pat06-图6. 公路村村通（30）

06-图6. 公路村村通（30）

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式说明：

输入数据包括城镇数目正整数N（<=1000）和候选道路数目M（<=3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式说明：

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出-1，表示需要建设更多公路。

样例输入与输出：

序号	输入	输出
1	6 15 1 2 5 1 3 3 1 4 7 1 5 4 1 6 2 2 3 4 2 4 6 2 5 2 2 6 6 3 4 6 3 5 1 3 6 1 4 5 10 4 6 8 5 6 3	12
2	3 1 2 3 2	-1
3	5 4 1 2 1 2 3 2 3 1 3 4 5 4	-1

提交代码

边是点的线性关系，因此用Kruskal算法。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<queue>
 6 #include<vector>
 7 #include<cmath>
 8 #include<string>
 9 using namespace std;
10 int f[1005];
11 struct node{
12     int u,v,cost;
13 };
14 bool cmp(node a,node b){
15     return a.cost<b.cost;
16 }
17 int findfa(int a){//返回父节点
18     if(a!=f[a]){
19         f[a]=findfa(f[a]);
20     }
21     return f[a];//注意，这里返回f[a]！！
22 }
23 int main(){
24     //freopen("D:\INPUT.txt","r",stdin);
25     int n,m;
26     scanf("%d %d",&n,&m);
27     int i;
28     node *load=new node[m];
29     for(i=0;i<=n;i++){
30         f[i]=i;
31     }
32     for(i=0;i<m;i++){
33         scanf("%d %d %d",&load[i].u,&load[i].v,&load[i].cost);
34     }
35     sort(load,load+m,cmp);
36     int num=1,cur=0,mincost=0;
37 
38     //cout<<num<<endl;
39 
40     /*for(i=0;i<m;i++){
41         cout<<load[i].cost<<endl;
42     }*/
43 
44     while(num<n&&cur<m){
45         int ufa=findfa(load[cur].u);
46         int vfa=findfa(load[cur].v);
47         if(ufa>vfa){
48             f[vfa]=ufa;
49             mincost+=load[cur].cost;
50             num++;
51         }
52         else{
53             if(vfa>ufa){
54                 f[ufa]=vfa;
55                 mincost+=load[cur].cost;
56                 num++;
57             }
58         }
59         cur++;
60     }
61 
62     if(num==n){
63         printf("%d
",mincost);
64     }
65     else{
66         printf("-1
");
67     }
68     delete []load;
69     return 0;
70 }