POJ1789-Truck History .

来源:转载

转载请注明出处:優YoU      http://user.qzone.qq.com/289065406/blog/1299323607

题意大概是这样的:用一个7位的string代表一个编号,两个编号之间的distance代表这两个编号之间不同字母的个数。一个编号只能由另一个编号“衍生”出来,代价是这两个编号之间相应的distance,现在要找出一个“衍生”方案,使得总代价最小,也就是distance之和最小。

例如有如下4个编号:

aaaaaaa

baaaaaa

abaaaaa

aabaaaa

显然的,第二,第三和第四编号分别从第一编号衍生出来的代价最小,因为第二,第三和第四编号分别与第一编号只有一个字母是不同的,相应的distance都是1,加起来是3。也就是最小代价为3。

问题可以转化为最小代价生成树的问题。因为每两个结点之间都有路径,所以是完全图。 

此题的关键是将问题转化为最小生成树的问题。每一个编号为图的一个顶点,顶点与顶点间的编号差即为这条边的权值,题目所要的就是我们求出最小生成树来。这里我用prim算法来求最小生成树。

 1 //Memory Time 
2 //15688K 344MS
3
4 #include<iostream>
5 #include<string>
6 using namespace std;
7
8 const int inf=10; //无穷大(两点间边权最大为7)
9 const int large=2001;
10
11 int n; //truck types
12 char str[large][8];
13 int dist[large][large]={0};
14
15 /*Compute Weight*/
16
17 int weight(int i,int j) //返回两个字符串中不同字符的个数(返回边权)
18 {
19 int w=0;
20 for(int k=0;k<7;k++)
21 if(str[i][k]!=str[j][k])
22 w++;
23 return w;
24 }
25
26 /*Prim Algorithm*/
27
28 int prim(void)
29 {
30 int s=1; //源点(最初的源点为1)
31 int m=1; //记录最小生成树的顶点数
32 bool u[large]; //记录某顶点是否属于最小生成树
33 int prim_w=0; //最小生成树的总权值
34 int min_w; //每个新源点到其它点的最短路
35 int flag_point;
36 int low_dis[large]; //各个源点到其它点的最短路
37
38 memset(low_dis,inf,sizeof(low_dis));
39 memset(u,false,sizeof(u));
40 u[s]=true;
41
42 while(1)
43 {
44 if(m==n) //当最小生成树的顶点数等于原图的顶点数时,说明最小生成树查找完毕
45 break;
46
47 min_w=inf;
48 for(int j=2;j<=n;j++)
49 {
50 if(!u[j] && low_dis[j]>dist[s][j])
51 low_dis[j] = dist[s][j];
52 if(!u[j] && min_w>low_dis[j])
53 {
54 min_w=low_dis[j];
55 flag_point=j; //记录最小权边中不属于最小生成树的点j
56 }
57 }
58 s=flag_point; //顶点j与旧源点合并
59 u[s]=true; //j点并入最小生成树(相当于从图上删除j点,让新源点接替所有j点具备的特征)
60 prim_w+=min_w; //当前最小生成树的总权值
61 m++;
62 }
63 return prim_w;
64 }
65
66 int main(void)
67 {
68 int i,j;
69
70 while(cin>>n && n)
71 {
72 /*Input*/
73
74 for(i=1;i<=n;i++)
75 cin>>str[i];
76
77 /*Structure Maps*/
78
79 for(i=1;i<=n-1;i++)
80 for(j=i+1;j<=n;j++)
81 dist[i][j]=dist[j][i]=weight(i,j);
82
83 /*Prim Algorithm & Output*/
84
85 cout<<"The highest possible quality is 1/"<<prim()<<'.'<<endl;
86
87 }
88 return 0;
89 }
我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b我的新浪微博:http://weibo.com/lyy289065406我的腾讯微博:http://t.qq.com/liao5422我的QQ空间:http://user.qzone.qq.com/289065406我的百度空间:http://hi.baidu.com/you289065406/home我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


分享给朋友:
您可能感兴趣的文章:
随机阅读: