题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1863
畅通工程
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 17593 Accepted Submission(s):
7417
Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。经过调查评估,得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序,计算出全省畅通需要的最低成本。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100
);随后的 N
行对应村庄间道路的成本,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间道路的成本(也是正整数)。为简单起见,村庄从1到M编号。当N为0时,全部输入结束,相应的结果不要输出。
行对应村庄间道路的成本,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间道路的成本(也是正整数)。为简单起见,村庄从1到M编号。当N为0时,全部输入结束,相应的结果不要输出。
Output
对每个测试用例,在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通,则输出“?”。
Sample Input
3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100
Sample Output
3
?
题目大意:实现任意两个村庄都有路,间接直接都可以,这里还有一个最小费用的问题,也就和平时做最短路是一样的,转换一下就好。
第一次用并查集的方法写最小生成树,需要学习和明白的地方就是需要排序(注意按照升序排列)这样先加上去的一定是最短~~
详见代码,也是第一次这样写,欢迎大家交流讨论哈!
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 int father[110],sum; 6 struct node 7 { 8 int s,d,f; 9 } p[110]; 10 11 bool cmp(const node &a,const node &b)//用来排序的,这里只需要给费用排序就可以了 12 { 13 return a.f<b.f; 14 } 15 16 void set(int n)//初始化,刚开始全部指向自己 17 { 18 for (int i=1; i<=n; i++) 19 father[i]=i; 20 } 21 22 int find(int a)//来查找是否属于同一个父节点,找最终的顶点 23 { 24 if (father[a]==a) 25 return a; 26 return father[a]=find(father[a]); 27 } 28 29 void Union(int x,int y,int z)//如果不是一个顶点的话,可以把这两个指向,连在一起 30 { 31 x=find(x); 32 y=find(y); 33 if (x!=y) 34 { 35 father[x]=y; 36 sum+=z; 37 } 38 } 39 40 int main() 41 { 42 int n,m,k; 43 while (cin>>n>>m) 44 { 45 if (n==0) 46 break; 47 sum=0,k=0; 48 set(m); 49 for (int i=1; i<=n; i++) 50 { 51 cin>>p[i].s>>p[i].d>>p[i].f; 52 } 53 sort(p,p+n,cmp); 54 for (int i=1; i<=n; i++) 55 { 56 Union(p[i].s,p[i].d,p[i].f); 57 } 58 for (int i=1; i<=m; i++)//这里就是来判断有几个地点,如果是一个顶点的话则成立 59 { 60 if (father[i]==i) 61 k++; 62 } 63 if (k>1) 64 printf ("?\n"); 65 else 66 printf ("%d\n",sum); 67 } 68 return 0; 69 }