hihocoder1097、1109最小生成树（prim算法+堆优化）

prim算法描述：

prim算法的思想和代码都跟dijkstra算法非常相似。

在dijkstra算法中，我们用每次取出未标记集合中到源点最近的点进行标记并更新其邻接点到源点的距离：当d[x]+w<d[y]时更新d[y]=d[x]+w。

而在prim算法中，我们只需要对dijkstra算法稍作改动即可，即只需要改变一下更新操作：当w<d[y]时更新d[y]=w，此时d[y]的含义是节点y连接到最小生成树的边的最小取值。也就是说，从图中某个节点发出了边可能有若干条，而最终将该节点连接到最小生成树上的那条必定是这些边中最短的。可以用反证法证明如下：如果从节点u发出的边中最短的边为(u, v)，我们假设将节点u连接到最小生成树上的边不是(u, v)而是其他的某条边，设在最小生成树上u到v的最短路径为u--p1--p2--...--pk--v，假设我们现在将边(u, p1)去掉，然后将边(u, v)连接起来，显然，这仍然是一棵生成树，且(u, v)这条边比(u, p1)这条边更短，因此我们现在这棵生成树比之前那棵生成树上所有边的权重和更小，这与我们最初的假设矛盾，所以最初的假设不成立，故原命题得证。最终，最小生成树的边权和为d数组所有元素之和。

我的代码：

 1 #include <iostream>
 2 #include <set>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 #define MAXN 1005
 8 #define INF 0x7fffffff
 9 
10 int w[MAXN][MAXN], n, d[MAXN];
11 bool onTree[MAXN];
12 
13 struct comp
14 {
15     bool operator()(const int &a, const int &b)const
16     {
17         if(d[a]==d[b]) return a<b;
18         return d[a]<d[b];
19     }
20 };
21 
22 void prim()
23 {
24     for(int i=1; i<=n; ++i) d[i] = INF;
25     d[1] = 0;
26     memset(onTree+1, 0, n);
27     set<int, comp> st;
28     for(int i=1; i<=n; ++i) st.insert(i);
29     while(!st.empty())
30     {
31         int x = *st.begin();
32         st.erase(x);
33         onTree[x] = true;
34         for(int y=1; y<=n; ++y)
35         {
36             if(y!=x&&!onTree[y]&&w[x][y]<d[y])
37             {
38                 st.erase(y);
39                 d[y] = w[x][y];
40                 st.insert(y);
41             }
42         }
43     }
44 }
45 
46 int main()
47 {
48     while(cin>>n)
49     {
50         for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) cin>>w[i][j];
51         prim();
52         int ans = 0;
53         for(int i=1; i<=n; ++i) ans += d[i];
54         cout<<ans<<endl;
55     }
56     return 0;
57 }

题目链接：http://hihocoder.com/problemset/problem/1097

 1 #include <iostream>
 2 #include <vector>
 3 #include <set>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 #define MAXN 100005
 9 #define INF 0x7fffffff
10 
11 struct edge
12 {
13     int y, w;
14     edge(int _y, int _w):y(_y),w(_w){}
15 };
16 
17 vector<edge> v[MAXN];
18 int n, m, d[MAXN];
19 bool onTree[MAXN];
20 
21 struct comp
22 {
23     bool operator()(const int &a, const int &b)const
24     {
25         if(d[a]==d[b]) return a<b;
26         return d[a]<d[b];
27     }
28 };
29 
30 void prim()
31 {
32     for(int i=1; i<=n; ++i) d[i] = INF;
33     d[1] = 0;
34     memset(onTree+1, 0, n);
35     set<int, comp> st;
36     for(int i=1; i<=n; ++i) st.insert(i);
37     while(!st.empty())
38     {
39         int x = *st.begin();
40         st.erase(x);
41         onTree[x] = true;
42         int sz = v[x].size();
43         for(int i=0; i<sz; ++i)
44         {
45             int y = v[x][i].y, w = v[x][i].w;
46             if(!onTree[y]&&w<d[y])
47             {
48                 st.erase(y);
49                 d[y] = w;
50                 st.insert(y);
51             }
52         }
53     }
54 }
55 
56 int main()
57 {
58     while(cin>>n>>m)
59     {
60         for(int i=1; i<=n; ++i) v[i].clear();
61         while(m--)
62         {
63             int x, y, w;
64             cin>>x>>y>>w;
65             v[x].push_back(edge(y, w));
66             v[y].push_back(edge(x, w));
67         }
68         prim();
69         int ans = 0;
70         for(int i=1; i<=n; ++i) ans += d[i];
71         cout<<ans<<endl;
72     }
73     return 0;
74 }

题目链接：http://hihocoder.com/problemset/problem/1109