prime(最小生成树)——POJ 1789

2024-09-05 04:18
文章标签 最小 生成 poj prime 1789

本文主要是介绍prime(最小生成树)——POJ 1789,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

对应POJ题目:点击打开链接


Truck History
Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u
Submit  Status  Practice  POJ 1789

Description

Advanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are used for vegetable delivery, other for furniture, or for bricks. The company has its own code describing each type of a truck. The code is simply a string of exactly seven lowercase letters (each letter on each position has a very special meaning but that is unimportant for this task). At the beginning of company's history, just a single truck type was used but later other types were derived from it, then from the new types another types were derived, and so on. 

Today, ACM is rich enough to pay historians to study its history. One thing historians tried to find out is so called derivation plan -- i.e. how the truck types were derived. They defined the distance of truck types as the number of positions with different letters in truck type codes. They also assumed that each truck type was derived from exactly one other truck type (except for the first truck type which was not derived from any other type). The quality of a derivation plan was then defined as 
1/Σ(to,td)d(to,td)

where the sum goes over all pairs of types in the derivation plan such that t  o is the original type and t  d the type derived from it and d(t  o,t  d) is the distance of the types. 
Since historians failed, you are to write a program to help them. Given the codes of truck types, your program should find the highest possible quality of a derivation plan. 

Input

The input consists of several test cases. Each test case begins with a line containing the number of truck types, N, 2 <= N <= 2 000. Each of the following N lines of input contains one truck type code (a string of seven lowercase letters). You may assume that the codes uniquely describe the trucks, i.e., no two of these N lines are the same. The input is terminated with zero at the place of number of truck types.

Output

For each test case, your program should output the text "The highest possible quality is 1/Q.", where 1/Q is the quality of the best derivation plan.

Sample Input

4
aaaaaaa
baaaaaa
abaaaaa
aabaaaa
0

Sample Output

The highest possible quality is 1/3.

题意:就是给你一些车牌号,然后你通过比较两个车牌号相同位置字符不同的个数作为权值,再一个完全图的最小生成树算法。


#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<iostream>
const int MAXN=2000+10;
const int INF=1<<30;
using namespace std;
int G[MAXN][MAXN];
int cp[MAXN];
int dis[MAXN];
int sum;
char truck[MAXN][10];void prim(int n, int v)
{int i,j;for(i=0; i<n; i++){dis[i]=G[v][i];cp[i]=v;}for(i=1; i<n; i++){int min=INF;int k=v;for(j=0; j<n; j++){if(dis[j] && dis[j]<min){min=dis[j];k=j;}}//printf("%d <-> %d = %d\n", cp[k], k, min);//打印两顶点与两点间权值sum+=dis[k];//计算最短路径和dis[k]=0;//加入集合for(j=0; j<n; j++){if(G[j][k] && G[j][k]<dis[j]){//更新候选边dis[j]=G[j][k];cp[j]=k;}}}printf("The highest possible quality is 1/%d.\n", sum);
}int Distance(char const *str1, char const *str2)
{const char *p;const char *q;int cnt=0;for(p = str1, q = str2; *p && *q;)if(*p++ != *q++) cnt++;return cnt;
}int main()
{//freopen("in.txt","r",stdin);int n;while(scanf("%d", &n), n)//节点为0~n-1{sum=0;int i,j;for(i=0; i<n; i++) scanf("%s", truck[i]);for(i=0; i<n; i++){//初始化图for(j=0; j<n; j++){if(i==j){ G[i][j]=0; continue;}G[i][j]=INF;}}for(i=0; i<n; i++){for(j=i+1; j<n; j++){int len = Distance(truck[i], truck[j]);G[i][j] = G[j][i] = len;}}prim(n, 0);}return 0;
}






这篇关于prime(最小生成树)——POJ 1789的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137923

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

C/C++随机数生成的五种方法

《C/C++随机数生成的五种方法》C++作为一种古老的编程语言,其随机数生成的方法已经经历了多次的变革,早期的C++版本使用的是rand()函数和RAND_MAX常量,这种方法虽然简单,但并不总是提供... 目录C/C++ 随机数生成方法1. 使用 rand() 和 srand()2. 使用 <random

Flask 验证码自动生成的实现示例

《Flask验证码自动生成的实现示例》本文主要介绍了Flask验证码自动生成的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习... 目录生成图片以及结果处理验证码蓝图html页面展示想必验证码大家都有所了解,但是可以自己定义图片验证码

Python如何在Word中生成多种不同类型的图表

《Python如何在Word中生成多种不同类型的图表》Word文档中插入图表不仅能直观呈现数据,还能提升文档的可读性和专业性,本文将介绍如何使用Python在Word文档中创建和自定义各种图表,需要的... 目录在Word中创建柱形图在Word中创建条形图在Word中创建折线图在Word中创建饼图在Word

nginx生成自签名SSL证书配置HTTPS的实现

《nginx生成自签名SSL证书配置HTTPS的实现》本文主要介绍在Nginx中生成自签名SSL证书并配置HTTPS,包括安装Nginx、创建证书、配置证书以及测试访问,具有一定的参考价值,感兴趣的可... 目录一、安装nginx二、创建证书三、配置证书并验证四、测试一、安装nginxnginx必须有"-

Java实战之利用POI生成Excel图表

《Java实战之利用POI生成Excel图表》ApachePOI是Java生态中处理Office文档的核心工具,这篇文章主要为大家详细介绍了如何在Excel中创建折线图,柱状图,饼图等常见图表,需要的... 目录一、环境配置与依赖管理二、数据源准备与工作表构建三、图表生成核心步骤1. 折线图(Line Ch

浅析如何使用Swagger生成带权限控制的API文档

《浅析如何使用Swagger生成带权限控制的API文档》当涉及到权限控制时,如何生成既安全又详细的API文档就成了一个关键问题,所以这篇文章小编就来和大家好好聊聊如何用Swagger来生成带有... 目录准备工作配置 Swagger权限控制给 API 加上权限注解查看文档注意事项在咱们的开发工作里,API