hdu 1879 继续畅通工程

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstdio>
 5 using namespace std;
 6 #define maxn 105
 7 int par[maxn];
 8 int n,m;
 9 int len;
10 struct node
11 {
12     int x;
13     int y;
14     int w;//这道题如果用double 出错，结果全为0
15 };
16 node e[maxn * (maxn - 1) / 2];
17 int cmp(const node &a , const node &b)
18 {
19     return a.w < b.w;
20 };
21 
22 int Find(int x)
23 {
24     int k,j,r;
25     r = x;
26     while(par[r] != r)
27         r = par[r];
28     k = x;
29     while(k != r)
30     {
31         j = par[k];
32         par[k] = r;
33         k = j;
34     }
35     return r;
36 }
37 int Merge(int x,int y)
38 {
39     int a = Find(x);
40     int b = Find(y);
41     if(a != b)
42     {
43         par[a] = par[b];
44         return 1;
45     }
46     return 0;
47 }
48 void input()
49 {
50     for(int i = 1; i <= n+5; i++)
51         par[i] = i;
52     len = 0;
53     int sta;
54     for(int i = 0; i < n*(n-1)/2; i++)
55     {
56         scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].w,&sta);
57         if(sta) e[i].w = 0;
58     }
59 }
60 
61 void make()
62 {
63     int all = n*(n-1)/2;
64     sort(e,e + all,cmp);
65     int t = n - 1;
66     for(int i = 0; t && i < all; i++)
67     {
68         if(Merge(e[i].x,e[i].y))
69         {
70             len += e[i].w;
71             t--;
72         }
73     }
74 }
75 int main()
76 {
77     freopen("input.txt","r",stdin);
78     while(scanf("%d",&n) && n)
79     {
80         input();
81         make();
82         printf("%d\n",len);
83     }
84 
85     return 0;
86 }