hdoj1863 畅通工程（Prime || Kruskal）

题目链接

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

思路

最小生成树问题，使用Prime算法或者Kruskal算法解决。这题在hdoj1233的基础上增加了判断是否能形成最小生成树的要求。

代码

Prime算法：

 1 #include <algorithm>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int INF = 0x7fffffff;
 7 const int N = 100 + 10;
 8 int map[N][N];
 9 int dist[N];
10 int n, m;
11 
12 void prime()
13 {
14     int min_edge, min_node;
15     for (int i = 1; i <= m; i++)
16         dist[i] = INF;
17     int ans = 0;
18     int now = 1;
19     for (int i = 1; i < m; i++)
20     {
21         dist[now] = -1;
22         min_edge = INF;
23         for (int j = 1; j <= m; j++)
24         {
25             if (j != now && dist[j] >= 0)
26             {
27                 if (map[now][j] > 0)
28                     dist[j] = min(dist[j], map[now][j]);
29                 if (dist[j] < min_edge)
30                 {
31                     min_edge = dist[j];    //min_edge存储与当前结点相连的最短的边
32                     min_node = j;
33                 }
34             }
35         }
36         if (min_edge == INF)    //不能形成最小生成树
37         {
38             puts("?");
39             return;
40         }
41         ans += min_edge;
42         now = min_node;
43     }
44     printf("%d
", ans);
45 }
46 
47 int main()
48 {
49     //freopen("hdoj1863.txt", "r", stdin);
50     while (scanf("%d%d", &n, &m) == 2 && n)
51     {
52         memset(map, 0, sizeof(map));
53         int a, b, d;
54         for (int i = 0; i < n; i++)
55         {
56             scanf("%d%d%d", &a, &b, &d);
57             map[a][b] = map[b][a] = d;
58         }
59         prime();
60     }
61     return 0;
62 }

Kruskal算法：

 1 #include <algorithm>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <vector>
 5 using namespace std;
 6 
 7 struct Edge
 8 {
 9     int a, b, dist;
10 
11     Edge() {}
12     Edge(int a, int b, int d):a(a),b(b),dist(d){}
13     bool operator < (Edge edge)    
14     {
15         return dist < edge.dist;
16     }
17 };
18 
19 const int N = 100 + 10;
20 vector<Edge> v;
21 int p[N];
22 int n, m;
23 
24 int find_root(int x)
25 {
26     if (p[x] == -1)
27         return x;
28     else return find_root(p[x]);
29 }
30 
31 void kruskal()
32 {
33     memset(p, -1, sizeof(p));
34     sort(v.begin(), v.end());    //将边按边长从短到长排序
35     int ans = 0;
36     for (int i = 0; i < v.size(); i++)
37     {
38         int ra = find_root(v[i].a);
39         int rb = find_root(v[i].b);
40         if (ra != rb)
41         {
42             ans += v[i].dist;
43             p[ra] = rb;
44         }
45     }
46 
47     int cnt = 0;
48     for (int i = 1; i <= m; i++)
49         if (p[i] == -1) cnt++;
50     if (cnt > 1)    //连通分量个数多于1个，不能形成最小生成树
51     {
52         puts("?");
53         return;
54     }
55     printf("%d
", ans);
56 }
57 
58 int main()
59 {
60     //freopen("hdoj1863.txt", "r", stdin);
61     while (scanf("%d%d", &n, &m) == 2 && n)
62     {
63         v.clear();
64         int a, b, d;
65         for (int i = 0; i < n; i++)
66         {
67             scanf("%d%d%d", &a, &b, &d);
68             v.push_back(Edge(a, b, d));
69         }
70         kruskal();
71     }
72     return 0;
73 }