【HDU3371】Connect the Cities（MST基础题）

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <cctype>
 7 #include <algorithm>
 8 #include <numeric>
 9 #include <limits.h>
10 
11 #define typec int
12 using namespace std;
13 
14 const typec inf = 0xffff;
15 const int V = 505;
16 int vis[V]; typec lowc[V];
17 int Map[V][V];
18 
19 typec prim (typec cost[][V], int n) {
20     int i, j, p;
21     typec minc, res = 0;
22     memset(vis, 0, sizeof(vis));
23     vis[0] = 1;
24     for (i = 1; i < n; ++ i) lowc[i] = cost[0][i];
25     for (i = 1; i < n; ++ i) {
26         minc = inf;
27         p = -1;
28         for (j = 0; j < n; ++ j) {
29             if (0 == vis[j] && minc > lowc[j]) {
30                 minc = lowc[j];
31                 p = j;
32             }
33         }
34         if (inf == minc) return -1;
35         res += minc;
36         vis[p] = 1;
37         for (j = 0; j < n; ++ j) {
38             if (0 == vis[j] && lowc[j] > cost[p][j]) {
39                 lowc[j] = cost[p][j];
40             }
41         }
42     }
43     return res;
44 }
45 
46 
47 int main () {
48     int n, road_n, union_n, T;
49     scanf("%d", &T);
50     while (T--) {
51         scanf("%d%d%d", &n, &road_n, &union_n);
52         //cout << "road_n : "  << road_n << endl;
53         for (int i = 0; i < V; ++ i) {
54             for (int j = 0; j < V; ++ j) {
55                 if (i == j) Map[i][j] = 0;
56                 else Map[i][j] = inf;
57             }
58         }
59 
60         for (int i = 0; i < road_n; ++ i) {
61             int x, y, w;
62             scanf("%d%d%d", &x, &y, &w);
63             Map[x - 1][y - 1] = Map[y - 1][x - 1] = min(Map[x - 1][y - 1], w);
64 
65         }
66         /*
67         for (int i = 0 ; i < n; ++ i) {
68             for (int j = 0; j < n; ++ j) {
69                 cout << Map[i][j] << "\t";
70             }
71             cout << endl;
72         }
73         */
74         for (int i = 0; i < union_n; ++ i) {
75             int xx, xx_n, last;
76             scanf("%d", &xx_n);
77             for (int j = 0; j < xx_n; ++ j) {
78                 scanf("%d", &xx);
79                 if (!j) {
80                     last = xx;
81                     continue;
82                 } else {
83                     Map[xx - 1][last - 1] = Map[last - 1][xx - 1] = 0;
84                     last = xx;
85                 }
86             }
87         }
88 
89         printf("%d\n", prim(Map, n));
90     }
91     return 0;
92 }