Truck History - poj 1789 (Prim 算法)
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 20884 | Accepted: 8075 |
Description
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 to is the original type and td the type derived from it and d(to,td) 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
Output
Sample Input
4
aaaaaaa
baaaaaa
abaaaaa
aabaaaa
0
Sample Output
The highest possible quality is 1/3.
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x0fffffff;
char str[][];
int map[][];
int vis[];
int d[];
int n;
int Prim(){
for(int i=;i<n;i++){
d[i]=INF;
vis[i]=;
}
d[]=;
int sum=;
for(int i=;i<n;i++){
int mi=INF;
int p;
for(int j=;j<n;j++){
if(!vis[j]&&mi>d[j]){
mi=d[j];
p=j;
}
}
sum+=mi;
vis[p]=;
for(int j=;j<n;j++){
if(!vis[j]){
d[j]= min(d[j],map[p][j]);
}
}
}
return sum;
}
int main() {
cin>>n;
while(n){
for(int i=;i<n;i++){
for(int j=;j<;j++){
cin>>str[i][j];
}
}
for(int i=;i<n;i++){
for(int j=i+;j<n;j++){
int sum=;
for(int k=;k<;k++){
if(str[i][k]!=str[j][k]){
sum++;
}
}
map[i][j]=map[j][i]=sum;
}
}
int sum=Prim();
cout<<"The highest possible quality is 1/"<<sum<<"."<<endl;
cin>>n;
}
return ;
}
最新文章
- 虚拟机下Linux读取USB设备的问题虚拟机下Linux无法读取USB设备的解决方案
- NTDLL未文档化函数RtlGetNtVersionNumbers获取操作系统版本
- 锤子banner
- sd_cms置顶新闻,背景颜色突击显示
- [Angular 2] Select From Multiple Nested Angular 2 Elements
- Android模拟器问题:No system images installed for this target
- 【Tomcat源码学习】-2.容器管理
- 【.net 深呼吸】自己动手来写应用程序设置类
- apigw鉴权分析(1-5)亚马逊 - 鉴权分析
- DriverManager 驱动管理器类简介 JDBC简介(三)
- UnicodeEncodeError: &#39;gbk&#39; codec can&#39;t encode character &#39;\xbb&#39; in position 30633: illegal multibyte sequence
- 视频修复工具recover_mp4,视频录制一半掉电,如何查看已保存数据?
- [转载]PHP中PSR-[0-4]规范
- Listener监听器和Filter过滤器
- 20165323《Java程序设计》第九周学习总结
- redis:order set有序集合类型的操作(有序集合)
- POJ3287(BFS水题)
- HDU1575-Tr 【矩阵快速幂】(模板题)
- poj2480-Longge&#39;s problem-(欧拉函数)
- go语言练习:sha256、sha512哈希算法
热门文章
- POJ 1769 Minimizing maximizer(DP+zkw线段树)
- [HDU6240]Server
- SQL 增删改查 复习
- Visio中插入公式
- 解决413 Request Entity Too Large
- ElasticSearch 排序
- 简谈WP,IOS,Android智能手机OS
- 转: Eclispe的远程开发
- [React] Use react-rewards to add microinteractions to React app to reward users for some actions
- 字体和颜色 Font Color 基础笔记