HDU 1879 继续畅通工程

http://acm.hdu.edu.cn/showproblem.php?pid=1879

题意：

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

思路：

最后的畅通工程。

 1 #include<iostream> 
 2 #include<cstring>
 3 #include<string>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<cmath>
 7 using namespace std;
 8 
 9 int n;
10 int ans;
11 int num;
12 
13 struct node
14 {
15     int u;
16     int v;
17     int w;
18 }edge[105*105];
19 
20 int p[105];
21 
22 int find(int x)
23 {
24     int r = x;
25     while (r != p[r])    r = p[r];
26     int i = x, j;
27     while (p[i] != r)
28     {
29         j = p[i];
30         p[i] = r;
31         i = j;
32     }
33     return r;
34 }
35 
36 bool cmp(node a, node b)
37 {
38     return a.w < b.w;
39 }
40 
41 void Kruskal()
42 {
43     for (int i = 0; i < n*(n-1)/2; i++)
44     {
45         int x = find(edge[i].u);
46         int y = find(edge[i].v);
47         if (x != y)
48         {
49             p[x] = y;
50             ans += edge[i].w;
51             num++;
52             if (num == n - 1)    return;
53         }
54     }
55 }
56 
57 int main()
58 {
59     //freopen("D:\txt.txt", "r", stdin);
60     int a, b, c, d;
61     while (~scanf("%d", &n) && n)
62     {
63         for (int i = 0; i <= n; i++)
64             p[i] = i;
65         num = 0;
66         for (int i = 0; i < n*(n - 1) / 2; i++)
67         {
68             scanf("%d%d%d%d", &a, &b, &c, &d);
69             edge[i].u = a;
70             edge[i].v = b;
71             edge[i].w = c;
72             if (d == 1)
73             {
74                 p[a] = b;
75                 num++;
76             }
77         }
78         sort(edge, edge + n*(n - 1) / 2, cmp);
79         ans = 0;
80         Kruskal();
81         printf("%d
", ans);
82     }
83 }