Description
省 政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表 中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。
Input
测 试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示 未建。
当N为0时输入结束。
当N为0时输入结束。
Output
每个测试用例的输出占一行，输出全省畅通需要的最低成本。
Sample Input
3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0
Sample Output
3 1 0
View Code
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<algorithm>
4 #include<string.h>
5 using namespace std;
6 struct node
7 {
8 int i, j, val, oo;
9 }T[5000];
10 bool cmp( node A, node B )
11 {
12 return A.val < B.val;
13 }
14 int set[5000];
15 void make_set()
16 {
17 for( int i = 0; i < 1000; i++ )
18 set[i] = i;
19 }
20 int find( int x )
21 {
22 return set[x] == x ? x: set[x]= find(set[x] );
23 }
24 int merge( int x, int y )
25 {
26 int x1 = find(x), y1 = find(y);
27 if( x1 != y1 )
28 {
29 set[x1] = y1;
30 }
31 }
32 int kruskal( int count )
33 {
34 sort( T, T+count, cmp );
35 int result = 0;
36 for( int i = 0; i < count; i++ )
37 {
38 if( find(T[i].i)!= find(T[i].j) )
39 {
40 merge( T[i].i , T[i].j );
41 result += T[i].val;
42 }
43 }
44 printf( "%d\n", result );
45 }
46 int main()
47 {
48 int n;
49 while( scanf( "%d", &n ), n )
50 {
51 make_set();
52 int count = 0;
53 for( int i = 1; i <= n*(n-1)/2; i++ )
54 {
55 scanf( "%d%d%d%d", &T[i].i,&T[i].j, &T[i].val, &T[i].oo );
56 count++;
57 if( T[i].oo )
58 {
59 int xx = find( T[i].i);
60 int yy = find( T[i].j );
61 if( xx != yy )
62 merge( xx, yy );
63 }
64 }
65 kruskal( count );
66 }
67 }