﻿ hdoj 1233 还是畅通工程

# 还是畅通工程

```3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0```

### Sample Output

```3
5```

``` 1 #include <queue>
2 #include <stdio.h>
3
4 using namespace std;
5 const int maxn=100+1;
6 int father[maxn];
7
8 struct edge{
9     int src, dest, cost;
10     bool operator <(const edge & nxt) const {
11         return cost>nxt.cost;
12     }
13 };
14 void init(int n){
15     for (int i=1;i<=n;i++){
16         father[i]=i;
17     }
18 }
19
20 int find(int a){
21     int x=a;
22     while(a!=father[a]){
23         a=father[a];
24     }
25     while(x!=father[x]){
26         int tmp=x;
27         x=father[x];
28         father[tmp]=a;
29     }
30     return a;
31 }
32
33 bool Union(int a , int b){
34     int x1=find(a);
35     int x2=find(b);
36     if (x1!=x2){
37         father[x1]=x2;
38         return true;
39     }else return false;
40 }
41
42 int main(){
43     edge e;
44     int n,m;
45     while(scanf("%d",&n)!=EOF && n ) {
46         priority_queue<edge> q;
47         init(n);
48         m=n*(n-1)/2;
49         while(m--){
50             scanf("%d%d%d", &e.src, &e.dest, &e.cost);
51             q.push(e);
52         }
53         int ans=0,count=0;
54         while(!q.empty()){
55             e=q.top();
56             q.pop();
57             if(Union(e.src,e.dest)){ //并查集来判断是不是成环
58                 count++;
59                 ans+=e.cost;
60             }
61             if(count==n-1) break;
62         }
63         printf("%d
",ans);
64     }
65     return 0;
66 }```