hdu1863 畅通工程---MST&连通

题目链接：

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

题目大意：

中文题，求MST权值，如果不连通，输出？

解题思路：

这道题帮我找出了之前模板中的一点小问题。

原来prim模板是迭代n次，实际是只需要迭代n-1次就求出了MST，由于有一个条件判断，所以迭代n次也无所谓。这道题在prim模板上加上判断连通的操作，如果某一次找不到为加入MST的最小边，说明图不连通。所以此处只能迭代n-1次，多迭代的话，会造成错误判断。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 100 + 10;
 5 const int INF = 0x3f3f3f3f;
 6 int Map[maxn][maxn];
 7 int lowcost[maxn], mst[maxn];
 8 int n, m;
 9 ll prim(int u)
10 {
11     ll ans = 0;
12     for(int i = 1; i <= n; i++)
13     {
14         lowcost[i] = Map[u][i];
15         mst[i] = u;
16     }
17     mst[u] = -1;
18     for(int i = 1; i < n; i++)
19     {
20         int minn = INF;
21         int v = -1;
22         //寻找lowcost数组里面的未加入mst的最小值
23         for(int j = 1; j <= n; j++)
24         {
25             if(mst[j] != -1 && lowcost[j] < minn)
26             {
27                 v = j;
28                 minn = lowcost[j];
29             }
30         }
31         if(v != -1)
32         {
33             mst[v] = -1;
34             ans += lowcost[v];
35             for(int j = 1; j <= n; j++)
36             {
37                 if(mst[j] != -1 && lowcost[j] > Map[v][j])
38                 {
39                     lowcost[j] = Map[v][j];
40                     mst[j] = v;
41                 }
42             }
43         }
44         else return 0;//没有找到，说明不连通
45     }
46     return ans;
47 }
48 int main()
49 {
50     while(scanf("%d%d", &m, &n) != EOF && m)
51     {
52         int u, v, w;
53         memset(Map, INF, sizeof(Map));
54         memset(lowcost, 0, sizeof(lowcost));
55         while(m--)
56         {
57             scanf("%d%d%d", &u, &v, &w);
58             Map[u][v] = Map[v][u] = w;
59         }
60         ll ans = prim(1);
61         if(ans)cout<<ans<<endl;
62         else cout<<"?"<<endl;
63     }
64     return 0;
65 }