孤岛连通工程

winston

作者：Hackbuteer1 发表于2012-2-16 19:31:49 原文链接

题目描述：
现在有孤岛n个，孤岛从1开始标序一直到n，有道路m条（道路是双向的，如果有多条道路连通岛屿i，j则选择最短的那条），请你求出能够让所有孤岛都连通的最小道路总长度。
输入：
数据有多组输入。
每组第一行输入n(1<=n<=1000),m(0<=m<=10000)。
接着m行，每行输入一条道路i j d(0<=d<=1000)，（i,j表示岛屿序号，d表示道路长度）。
输出：
对每组输入输出一行，如果能连通，输出能连通所有岛屿的最小道路长度，否则请输出字符串"no"。
样例输入：3 5
1 2 2
1 2 1
2 3 5
1 3 3
3 1 2
4 2
1 2 3
3 4 1样例输出：3
no

2. #include<iostream>
3. #include<algorithm>
4. using namespace std;
5. #include<stdio.h>
7. struct Edge
8. {
9.         int x;
10.         int y;
11.         int cost;
12. }edge[10001];
13. int set[10001];
15. inline int find(int x)           //带路径优化的并查集查找算法
16. {
17.     int i,j,r;
18.     r=x;
19.     while(set[r]!=r)
20.         r=set[r];
21.     i=x;
22.     while(i!=r)
23.     {
24.         j=set[i];
25.         set[i]=r;
26.         i=j;
27.     }
28.     return r;
29. }
30. inline void merge(int x,int y)     //优化的并查集归并算法
31. {
32.     int t=find(x);
33.     int h=find(y);
34.     if(t<h)
35.         set[h]=t;
36.     else
37.         set[t]=h;
38. }
40. /*
41. int cmp(const void *a,const void *b)
42. {
43.         return((*(struct Edge *)a).cost-(*(Edge *)b).cost);
44. }
45. */
47. bool cmp(const Edge& a,const Edge& b)
48. {
49.         return a.cost<b.cost;
50. }
52. void init(int n)          //初始化并查集，各点为孤立点，分支数为n
53. {
54.         for(int i=1;i<=n;i++)
55.                 set[i]=i;
56. }
57. int kruskal(int n,int m)
58. {
59.         int i,num,sum,from,to;
60.         //qsort(edge,m,sizeof(edge[0]),cmp);
61.         sort(edge,edge+m,cmp);
62.         sum=num=0;
63.         for(i=0;i<m;i++)
64.         {
65.                 from = find(edge[i].x);    //判断线段的起始点所在的集合  
66.                 to = find(edge[i].y);      //判断线段的终点所在的集合
67.                 if(from != to)        //如果线段的两个端点所在的集合不一样  
68.                 {
69.                         merge(from,to);    //合并两个集合
70.                         sum+=edge[i].cost;
71.                         num++;
72.                 }
73.                 if(num==n-1)
74.                         break;
75.         }
76.         if(num<n-1)
77.                 return -1;
78.         else
79.                 return sum;
80. }
82. int main(void)
83. {
84.         int i,n,m,k;
85.         while(scanf("%d %d",&n,&m)!=EOF)
86.         {
87.                 for(i=0;i<m;i++)
88.                 {
89.                         scanf("%d %d %d",&edge[i].x,&edge[i].y,&edge[i].cost);
90.                 }
91.                 init(n);
92.                 k=kruskal(n,m);
93.                 if(k==-1)
94.                         printf("no\n");
95.                 else
96.                         printf("%d\n",k);
97.         }
98.         return 0;
99. }

复制代码