用 prim 解决一个最小生成树板子题

 1 #include<cstdio>
 2 #include<cstring>
 3 
 4 const int INF = 0x3f3f3f3f;
 5 
 6 int n, m;
 7 int G[105][105];
 8 
 9 bool read_input() {
10     if(scanf("%d%d", &n, &m) == 2 && !n) return false;
11     memset(G, INF, sizeof(G));
12     int u, v, e;
13     for(int i = 0; i != n; ++i) {
14         scanf("%d%d%d", &u, &v, &e);
15         if(e < G[u][v]) {
16             G[u][v] = G[v][u] = e;
17         }
18     }
19     return true;
20 }
21 
22 int dis[105];
23 int vis[105];
24 void prim() {
25     int sum = 0;
26     int cnt = 1;
27     for(int i = 1; i <= m; ++i) {
28         dis[i] = G[1][i];
29         vis[i] = 0;
30     }
31     vis[1] = 1;
32     for(int i = 0; i != m-1; ++i) {
33         int minn = INF;
34         int t = 1000;
35         for(int j = 1; j <= m; ++j) {
36             if(!vis[j] && dis[j] < minn) {
37                 minn = dis[j];
38                 t = j;
39             }
40         }
41         if(t == 1000) break;
42         sum += minn;
43         vis[t] = 1;
44         cnt++;
45         for(int j = 1; j <= m; ++j) {
46             if(!vis[j] && dis[j] > G[t][j]) {
47                 dis[j] = G[t][j];
48             }
49         }
50     }
51     if(cnt == m) printf("%d\n", sum);
52     else printf("?\n");
53 }
54 
55 int main() {
56     while(read_input()) {
57         prim();
58     }
59     return 0;
60 }