poj2421ConstructingRoads解题报告

1 #include
2 #include
3 using namespace std;
4
5 const int maxe &＃61; 10000 &＃43; 10; // 这里开小点也行&＃xff0c;因为只存储矩阵不够一半的数据
6 int rep[maxe], vis[maxe];
7
8 struct sets
9 {
10 int v1, v2;
11 int value;
12 } exa[maxe];
13
14 int cmp(sets a, sets b)
15 {
16 return a.value < b.value;
17 }
18
19 int find(int x)
20 {
21 return x &＃61;&＃61; rep[x] ? x : find(rep[x]);
22 }
23
24 int main()
25 {
26 int i, j, n, a, b, x, y, t, cnt, flag;
27 while (scanf("%d", &n) !&＃61; EOF)
28 {
29 for (i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)
30 {
31 rep[i] &＃61; i;
32 }
33 cnt &＃61; 0;
34 for (i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)
35 {
36 for (j &＃61; 1; j <&＃61; n; j&＃43;&＃43;)
37 {
38 scanf("%d", &a);
39 if (i // 只存储上三角矩阵
40 {
41 exa[cnt].v1 &＃61; i;
42 exa[cnt].v2 &＃61; j;
43 exa[cnt].value &＃61; a;
44 cnt&＃43;&＃43;;
45 }
46 }
47 }
48 sort(exa, exa&＃43;cnt, cmp); // 对长度进行从小到大排序
49 flag &＃61; 0;
50 memset(vis, 0, sizeof(vis));
51 scanf("%d", &t);
52 while (t--)
53 {
54 scanf("%d%d", &a, &b);
55 if (a > b)
56 swap(a, b); // 刚开始就保持小的元素的祖先是大的元素
57 x &＃61; find(a);
58 y &＃61; find(b);
59 if (x > y)
60 {
61 swap(x, y); // 合并集合的时候&＃xff0c;有可能使得大的元素的祖先变成了是比它小的元素
62 }
63 if (vis[a] && vis[b]) // 两个村庄在之前已经被访问过&＃xff0c;这是为了处理情况4的情况的
64 rep[x] &＃61; y;
65 else
66 {
67 if (x &＃61;&＃61; y) // 所有村庄都有路可通
68 flag &＃61; 1;
69 if (!vis[a] && !vis[b])
70 {
71 rep[x] &＃61; y;
72 vis[a] &＃61; vis[b] &＃61; 1;
73 }
74 else if (!vis[a])
75 {
76 rep[x] &＃61; y;
77 vis[a] &＃61; 1;
78 }
79 else if (!vis[b])
80 {
81 rep[x] &＃61; y;
82 vis[b] &＃61; 1;
83 }
84 }
85 }
86 if (!flag)
87 {
88 int minval &＃61; 0;
89 for (i &＃61; 0; i )
90 {
91 x &＃61; find(exa[i].v1);
92 y &＃61; find(exa[i].v2);
93 if (x !&＃61; y)
94 {
95 minval &＃43;&＃61; exa[i].value;
96 if (x < y) // 为了与前面相一致&＃xff0c;也是小的元素的祖先是大的元素
97 rep[x] &＃61; y;
98 else
99 rep[y] &＃61; x;
100 }
101 }
102 printf("%d\n", minval);
103 }
104 else
105 printf("0\n");
106 }
107 return 0;
108 }