试题、程序及解题报告2007acm暑期集训基础篇mst

1、最小生成树 MST (minimum spanning tree) by nkzgm最小生成树定义bchifaedg48812414791067211对于一个无向连通图G=(V,E),其中V是顶点集合，E是边的集合，对于E中每一条边(u,v),都有一个权值w(u,v)表示连接u和v的代价。我们希望找出一个无回路的子集T(属于E),它连接了所有的顶点，且其权值之和w(T)= w(u,v) (u,v)属于T为最小。因为T无回路且连接所有的顶点，所以它必然是一棵树，称为生成树(spanning tree),因为它“生成”了图G。把确定树T的问题称为最小生成树问题。下图展示一个连通图及其最小生成树的实

2、例。最小生成树求最小生成树的方法主要有以下两种贪心策略：Prim算法Kruskal算法 Prim算法贪心准则加入后仍形成树，且耗费最小始终保持树的结构Kruskal算法是森林算法过程从单一顶点的树T开始不断加入耗费最小的边(u, v)，使T(u, v)仍为树 u、v中有一个已经在T中，另一个不在T中Prim 算法过程bchifaedg488414791067211aidcbhgfe12全部节点都被覆盖，算法结束Prim算法的性能Prim算法的性能取决于如何选取下一个适合条件的最小权值边，因为最小生成树必定有V-1个边，因而选取操作必须进行V-1次。朴素的方法是用邻接矩阵，线性扫描。复杂度为O(

3、V*V)。（用于稠密图）如果用二叉最小堆来实现，可以优化到O(ElgV)。（用于稀疏图）如果使用斐波那契堆，运行时间可以改进为O(E+VlgV)。 （用于稀疏图） Kruskal算法每个步骤选择一条边加入生成树贪心准则：不会产生环路，且耗费最小可按耗费递增顺序考察每条边若产生环路，丢弃否则，加入Kruskal 算法过程bchifaedg488414791067211aidcbhgfe12构成环路构成环路构成环路全部节点都被覆盖，算法结束Kruskal算法的性能Kruskal也需要进行V-1次选取操作，它的选取范围是整个图，因而可以用O(ElgE)的时间对所有的边进行排序。从这个有序的排列依次选

4、取，若选取的边的加入不能构成回路，则加入。否则对排列的下一个边进行相同操作。直到选取了V-1个边为止。在判断是否构成回路时需要用并查集。Kruskal的运行时间为O(ElgE)。Prim 和 Kruskal的区别Prim和Kruskal的贪心策略是一样的，都是选取耗费最小的边，只不过选取的范围不同：对于Prim，其选取的边(u,v)必有一个顶点已经被覆盖，另一个顶点未被覆盖。而对于Kruskal,其选取的边(u,v)任意，只要这个边的加入不能使被覆盖的顶点构成回路。下面看一个例子： Agri-Net Description Farmer John has been elected mayor

5、of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course. Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum

6、amount of optical fiber to connect his farm to all the other farms. Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one

7、 farm to any other farm. The distance between any two farms will not exceed 100,000. Input The input includes several cases. For each case, the first line contains the number of farms, N (3 = N = 100). The following lines contain the N x N conectivity matrix, where each element shows the distance fr

8、om on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.Output For ea

9、ch case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms. Sample Input4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 Sample Output28 这个题目，实际上是给了N个顶点，每两个顶点间的距离已经给出，让你求一条最小权值的路径，该路径使得所有的farms能够相互到达。这是典型的最小生成树。分析2431421816179代码：(朴素prim）

10、#includeint main() int i,j,k,n,a101101; while(scanf(%d,&n)!=EOF) for(i=1;i=n;i+) for(j=1;j=n;j+) scanf(%d,&aij); int flag101=0,sum=0; /flagi用来标记节点i是否被覆盖 flag1=1; /选取第一个点 for(k=1;kn;k+) /循环n-1次 int min=-1,min_i; for(i=1;i=n;i+) /选取下一个最小权值的节点 if(flagi=0&(min=-1|a1imin) min=a1i; min_i=i; flagmin_i=1; /

11、覆盖节点 for(i=1;iamin_ii) a1i=amin_ii; sum+=a1min_i; /加上权值 printf(%dn,sum); return 0;相关题目：NKOJ:1201: Arctic Network 1755: QS Network 1676: NetworkingPOJ: 2421: Constructing Roads 1258: Agri-Net谢谢大家后面的幻灯片作为补充，给出了并查集，最小堆的简单介绍，以及相关程序。有精力的同学可以进一步学习研究。并查集Kruskal算法需要用到并查集，并查集实现程序如下：int *parent;void initializ

12、e(int n)/初始化，每个类/树有一个元素parent=new intn+1;for(int e=1;e=n;e+)parente=0;int Find(int e)/返回包含e的树的根节点while(parente)e=parente; /上移一层return e;void Union(int i,int j) /将根为i和j的两棵树进行合并parentj=i;并查集为了防止树变成一条单链的最坏情况，在进行合并时，可以用重量规则进行合并。将重量小的树合并到重量大的树中。bool *root; int *parent;/若当前节点为根，则root为true/parent用来保存该树中节点的

13、总数void Initialize(int n)root=new booln+1;parent=new intn+1;for(int e=1;e=n;e+)parente=1; roote=true;int Find(int e)while(!roote) e=parente;return e;void Union(int i,int j)if(parentiparentj)parentj+=parenti;rooti=false;parenti=j;elseparenti+=parentj;rootj=false;parentj=I;Kruskal算法的实现并查集还有其他优化策略，比如路径压

14、缩，这里不再论述。对于kruskal算法，在判断加入的边(u,v)是否构成回路时，只需判断Find(u)与Find(v)是否相等即可。若相等，则构成回路，否则不构成回路。例子的kruskal程序如下：#include #include #include using namespace std;#define N 10000struct Edge int u,v,w;class UFset private: bool *root; int *parent; int n;public: UFset(int n) int i; this-n=n; root=new booln; parent=new

15、 intn; for(i=0;in;i+) parenti=1; rooti=true; UFset() delete parent; delete root; int Find(int e) / Return root of tree containing e. / Compact path from e to root. int i=e; / Find root while(!rooti) i=parenti; / compact int j=e;/ start at e while(j!=i)/ j is not root int pj=parentj; parentj=i;/ move

16、 j to level 2 j=pj;/ j moves to old parent return i; Kruskal算法的实现 bool Union(int x,int y) / Combine trees with roots px and py. int px=Find(x); int py=Find(y); if(px=py) return false; if(parentpxparentpy) / px es subtree of py parentpy+=parentpx; rootpx=false; parentpx=py; else / py es subtree of px

17、 parentpx+=parentpy; rootpy=false; parentpy=px; return true; ;class graph public: int n,m; Edge edgeN; void kruskal();bool cmp(const Edge &e1,const Edge &e2) return e1.we2.w;void graph:kruskal() sort(edge,edge+m,cmp); UFset ufset(n); int min=0,k=0; for(int i=0;im;i+) if(ufset.Union(edgei.u,edgei.v)

18、min+=edgei.w; +k; if(k=n-1) break; printf(%dn,min);Kruskal算法的实现graph g;int main() int i,j,w; while(scanf(%d,&g.n)!=EOF) int k=0; for(i=0;ig.n;i+) for(j=0;jg.n;j+) scanf(%d,&w); if(ij) g.edgek.u=i; g.edgek.v=j; g.edgek.w=w; k+; g.m=k; g.kruskal(); return 0;最小堆最小堆是最小的完全二叉树，其每个节点的值都小于或等于其子女节点（如果有的话）的值。

19、最小堆可以用数组存储，根节点放在a1,依次进行存储。例如：2847a110a5a4a3a2最小堆有两种操作，分别是插入和删除操作。最小堆的插入插入顺序为2 8 4 10 7：2748a110a5a4a3a2堆为空，第一个数2插入到a1第二个数8插入到a2,满足每个节点都小于等于其子节点的值第三个数4插入到a3,满足每个节点都小于等于其子节点的值第四个数10插入到a4,满足每个节点都小于等于其子节点的值第五个数7插入到a5不满足每个节点都小于等于其子节点的值,需要进行调整。将7上移到其父节点a2,8下移到a5此时所有节点都满足节点值小于等于其子节点的值。若不满足，继续上移。最小堆的删除从最小堆中

20、删除最小值：最小堆的最小值肯定是a1,将a1的值取出,同时将数组的最后一个值a5赋值给a1,再删除a5。此时节点a1不满足最小堆的条件,取节点a1子节点a2,a3的最小值a3(值为4),将4赋值给a1,将a1的原值8赋值给a3,此时所有节点都满足条件。若a3不满足条件,继续向下移动。2847a110a5a4a3a28最小堆插入程序：/node为节点结构,CurrentSize为数组大小/node aN;void Insert(node& x) int i = +CurrentSize; /插入一个节点，数组大小加1 while(i!=1 & xai/2) /若堆不为空并且插入节点的值小于其父节

21、点的值 ai=ai/2;/父节点的值下移 i/=2; /上移 ai=x; /i为1或节点i的值ai大于ai/2删除程序：void DeleteMin(node& x) x = a1; /最小值为a1 node y = aCurrentSize-; int i=1,ci=2; /ci为i的子节点 while (ci=CurrentSize) if(ciaci+1) ci+; /选取节点i子节点最小的一个 if(y=yPrim的最小堆实现/vectorvi存储从i出发的边/heapN存储最小堆#include#include#includeusing namespace std; #define

22、N 1001#define INF 130struct node int id,val; /id为节点编号，val为边的权值 bool operator (node s) return val (node s) return vals.val; bool operator=(node s) return val=s.val; bool operator=(node s) return val=(node s) return val=s.val; node operator= (node s) id=s.id; val=s.val; return *this;class Graph privat

23、e: int CurrentSize; node heapN; public: int n,m; vectorvN; void Insert(node& x); void DeleteMin(node& x); int Prim(int);void Graph:Insert(node& x) int i = +CurrentSize; while(i!=1 & xheapi/2) heapi=heapi/2; i/=2; heapi=x;Prim的最小堆实现void Graph:DeleteMin(node& x) x = heap1; node y = heapCurrentSize-; int i=1,ci=2; while (ci=CurrentSize) if(cihe