最小生成树的概念
给定无向图G = (V, E)，连接G中所有点，且边集是E的子集的树称为G的生成树，而权值和最小的生成树称为最小生成树，即MST。
构造MST的方法有很多种。常用的有Kruskal算法和Prim算法，前者好写，时间复杂度为O(m)，后者稍微难写，时间复杂度O(n*n)。(n为树的节点数，m为边数)。
Kruskal算法(摘自刘汝佳白书P199)：
算法的第一步是给所有边按照从小到大的顺序排序，然后从小到大考查所有边。考查到边(u, v)的时候有两种情况：
情况1：u, v此时属于同一个连通分量中，则加入(u, v)会形成环，不能加入该边。
情况2：u, v属于不同的连通分量。那么加入(u, v)一定是最优情况。为什么呢？用反证法证。如果不加这条边得到最优解T，则T+(u,v)一定有且只有一个环，而且环中至少有一条边(u', v')权值大于或等于(u, v)。删除该边后，得到新树T' = T + (u,v) - (u', v')，权值和T <= T，所以加入(u, v)不会比不加入差。
算法中，判断是否属于同一个连通分量用并查集即可。
1 //Kruskal算法求MST，返回MST的权值和，如果不联通返回-1 2 //时间复杂度O(m) 3 4 struct Pat{ //表示边 5 int s, e, w; //s, e表示边的两个点，w为权值 6 }; 7 8 int f[N]; //并查集 9 10 int kruskal(int n, int m) //n为点的数量，m为边的数量 11 { 12 sort (p, p+m, cmp); 13 for (int i = 0; i < n; ++ i) 14 f[i] = i; 15 16 int cost = 0; 17 for (int i = 0; i < m; ++ i){ 18 int t1 = find(p[i].s), t2 = find(p[i].e); 19 if (t1 != t2){ 20 cost += p[i].w; 21 f[t1] = t2; 22 } 23 } 24 25 int tmp; 26 for (int i = 0; i < n; ++ i){ 27 if (!i) tmp = find(i); 28 else if (tmp != find(i)) return -1; 29 } 30 return cost; 31 }
Prim算法：
详见我的另一篇文章，http://www.cnblogs.com/plumrain/p/Prim_Dijskra.html。比较讨论Dijskra和Prim算法的。
1 //Prim算法求MST，返回MST的权值和，如果图不联通返回-1 2 //时间复杂度O(n*n) 3 //这代码是用优先队列priority_queue写的，其实用set来写会快一些。 4 5 typedef pair<int, int> pii; 6 const int N = ; //N表示节点数 7 8 int c[N]; //c[i]表示i点目前到已选出的点中最短边的权值 9 bool v[N]; //v[i] = 0表示i点目前还没有被选出 10 vector<pii> p[N]; //p[i]表示一点为i的边，另一点为p[i][j].first，该边权值为p[i][j].second 11 12 int prim(int n, int m) //n为节点数，m为边数 13 { 14 int cost = 0; 15 CLR (v); 16 priority_queue<pii, vector<pii>, cmp> q; 17 while (!q.empty()) q.pop(); 18 19 for (int i = 1; i < n; ++ i) 20 c[i] = maxint - 1000; 21 c[0] = 0; 22 v[0] = 1; 23 for (int i = 0; i < (int)p[0].size(); ++ i){ 24 pii tmp = p[0][i]; 25 c[tmp.first] = tmp.second; 26 q.push (make_pair(tmp.first, tmp.second)); 27 } 28 29 for (int i = 0; i < n-1; ++ i){ 30 if (q.empty()) break; 31 pii tmp = q.top(); q.pop(); 32 while (v[tmp.first] && !q.empty()){ 33 tmp = q.top(); q.pop(); 34 } 35 if (v[tmp.first]) break; 36 37 int t1 = tmp.first, t2 = tmp.second; 38 cost += t2; 39 v[t1] = 1; 40 c[t1] = 0; 41 for (int j = 0; j < (int)p[t1].size(); ++ j) if (!v[p[t1][j].first]){ 42 pii t = p[t1][j]; 43 if (c[t.first] > t.second){ 44 q.push (make_pair(t.first, t.second)); 45 c[t.first] = t.second; 46 } 47 } 48 } 49 50 for (int i = 0; i < n; ++ i) 51 if (!v[i]) return -1; 52 return cost; 53 }
题目训练：
虽然在网上挂了一个专题，但是做了以后才发现里面几乎都是裸题。所以就挑其中一些题来写题解，以后碰到好题再添加。
1、HDU 1863，HDU 1875，HDU 1879，HDU 1233
畅通工程系列，都是很裸的MST的题。贴一篇题解，http://www.cnblogs.com/plumrain/p/HDU_changtong.html。
2、POJ 2349 Arctic Network
对于给定图，求其生成树的第k大的边最小为多少。其实很容易想到用MST，但是关键是为什么。要证明也不容易。http://www.cnblogs.com/plumrain/p/POJ_2349.html
3、POJ 1679 The Unique MST
问最小生成树是否唯一。http://www.cnblogs.com/plumrain/p/POJ_1679.html
4、这是我目前做过的一些水题：ZOJ 1586，HDU 1102(POJ 2421)，POJ 1251(HDU 1301)，POJ 1287，POJ 2031，POJ 1789，POJ 1751，POJ 1258，POJ 3026