最小生成树的概念　

　　　给定无向图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算法：

　　　详见我的另一篇文章，。比较讨论Dijskra和Prim算法的。

1 //Prim算法求MST，返回MST的权值和，如果图不联通返回-1 2 //时间复杂度O(n*n) 3 //这代码是用优先队列priority_queue写的，其实用set来写会快一些。 4  5 typedef pair
      
        pii; 6 const int N = ;                         //N表示节点数 7  8 int c[N];                               //c[i]表示i点目前到已选出的点中最短边的权值 9 bool v[N];                              //v[i] = 0表示i点目前还没有被选出10 vector
       
         p[N];                       //p[i]表示一点为i的边，另一点为p[i][j].first，该边权值为p[i][j].second11 12 int prim(int n, int m)                  //n为节点数，m为边数13 {14     int cost = 0;15     CLR (v);16     priority_queue
        
         , 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的题。贴一篇题解，。

 

2、POJ 2349 Arctic Network

　　　对于给定图，求其生成树的第k大的边最小为多少。其实很容易想到用MST，但是关键是为什么。要证明也不容易。

 

3、POJ 1679 The Unique MST

　　　问最小生成树是否唯一。

 

4、这是我目前做过的一些水题：ZOJ 1586，HDU 1102(POJ 2421)，POJ 1251(HDU 1301)，POJ 1287，POJ 2031，POJ 1789，POJ 1751，POJ 1258，POJ 3026