继续畅通工程

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18078 Accepted Submission(s): 7820

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。

Input

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

当N为0时输入结束。

Output

每个测试用例的输出占一行，输出全省畅通需要的最低成本。

Sample Input

Sample Output

3
1
0

俗称的避圈法，用UFS判断是否成环。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 #include <stack>
10 #include <list>
11 #include <vector>
12 
13 using namespace std;
14 
15 const int maxn = 1001;
16 
17 typedef struct Node {
18     int x;
19     int y;
20     int v;
21     bool ok;
22 }Node;
23 
24 Node city[maxn*maxn/2];
25 int pre[maxn], n, m, num;
26 
27 bool cmp(Node a, Node b) {
28     if(a.ok != b.ok) {
29         return a.ok < b.ok;
30     }
31     return a.v < b.v;
32 }
33 
34 int find(int x) {
35     return x == pre[x] ? x : pre[x] = find(pre[x]);
36 }
37 bool unite(int x, int y) {
38     x = find(x);
39     y = find(y);
40     if(x != y) {    
41         num++;
42         pre[x] = y;
43         return 1;
44     }
45     return 0;
46 }
47 
48 inline void init() {
49     for(int i = 0; i <= n; i++) {
50         pre[i] = i;
51     }
52 }
53 
54 int solve(){
55     int ans = 0;
56     for(int i = 1; i <= m; i++) {
57         if(num >= n - 1) {
58             break;
59         }
60         if(unite(city[i].y, city[i].x)) {   //原本是否畅通？
61             ans += city[i].v * city[i].ok;
62         }
63     }
64     return ans ;
65 }
66 int main() {
67     // freopen("in", "r", stdin);
68     // ios::sync_with_stdio(false);
69     while(scanf("%d", &n) && n) {
70         init();
71         m = n * (n - 1) / 2;
72         int ok;
73         num = 0;
74         for(int i = 1; i <= m; i++){
75             scanf("%d %d %d %d", &city[i].x, &city[i].y, &city[i].v, &ok);
76             city[i].ok = ok ? 0 : 1;    //反过来
77         }
78         sort(city + 1, city + m + 1, cmp);
79         printf("%d
", solve());
80     }   
81     return 0;
82 }