用 prim 和kruskal 解决最小生成树板子题

// hdu 1863

//http://acm.hdu.edu.cn/showproblem.php?pid=1863

 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
", sum);
52     else printf("?
");
53 }
54 
55 int main() {
56     while(read_input()) {
57         prim();
58     }
59     return 0;
60 }

// hdu 1301

// http://acm.hdu.edu.cn/showproblem.php?pid=1301

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n;
 7 int p[300];
 8 
 9 struct node {
10     char x, y;
11     int len;
12 } edge[100];
13 
14 int cmp(node a, node b) { return a.len < b.len; }
15 int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
16 
17 int main() {
18     while(scanf("%d", &n) == 1 && n) {
19         char s, e;
20         int m, v, k, ans;
21         k = 0;
22         ans = 0;
23         for(int i = 0; i != 300; ++i) { p[i] = i; }
24 
25         for(int i = 0; i != n-1; ++i) {
26             getchar();
27             scanf("%c%d", &s, &m);
28             for(int j = 0; j != m; ++j) {
29                 getchar();
30                 scanf("%c%d", &e, &v);
31                 edge[k].x = s;
32                 edge[k].y = e;
33                 edge[k].len = v;
34                 k++;
35             }
36         }
37         sort(edge, edge+k, cmp);
38         for(int i = 0; i != k; ++i) {
39             int x = find(edge[i].x);
40             int y = find(edge[i].y);
41             if(x != y) {
42                 ans += edge[i].len;
43                 p[x] = y;
44             }
45         }
46         printf("%d
", ans);
47     }
48     return 0;
49 }