最小生成树并查集最短路.ppt

最小生成树并查集最短路,罗方炜lfw2565295,最小生成树,问题描述：某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。,最小生成树,输入：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N(100)；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。当N为0时，输入结束，该用例不被处理。输出：对每个测试用例，在1行里输出最小的公路总长度。,最小生成树,样例输入：312113223441211341412332423450样例输出：35,最小生成树,最小生成树：在一个具有几个顶点的连通图G中，如果存在子图G包含G中所有顶点和一部分边，且不形成回路，则称G为图G的生成树，代价最小生成树则称为最小生成树。简称MST。,最小生成树,一般有两种算法：Prim和Kruskal算法今天主要讲Kruskal算法，适用本题，给出的边数，复杂度elong(e)(其中e表示变数),最小生成树,算法粗略描述：假设WN=(V,E)是一个含有n个顶点的连通网，先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。,最小生成树,做法:定义结点：#defineM10005structnodeintx,y,w;/表示x到y需要花费weM;intn,m,fatherM;/n定点数量，m边数量，fatherM,每个定点所属集合,最小生成树,intkruskal()intres=0,k=1,j=0;for(inti=1;i=m;i+)fatheri=i;/初始化集合数组while(kn,最小生成树,intmain()while(scanf(%d,最小生成树,整体思想已经完成，但是可以看到第二部分红色字体标出的代码：sn1=findroot(m1),sn2=findroot(m2);unionset(sn1,sn2);这部分涉及到了集合操作，也就是我们马上要讲的并查集,并查集,英文：DisjointSet，即“不相交集合”将编号分别为1N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合。常见两种操作：合并两个集合查找某元素属于哪个集合,所以，也称为“并查集”,并查集,用编号最小的元素标记所在集合；定义一个数组set1.n，其中seti表示元素i所在的集合；,i,Set(i),不相交集合：1,3,7,4,2,5,9,10,6,8,并查集,find1(x)returnsetx;,Merge1(a,b)i=min(a,b);j=max(a,b);for(k=1;k=N;k+)if(setk=j)setk=i;,(1),(N),并查集,对于“合并操作”，必须搜索全部元素！,树结构如何？,并查集,每个集合用一棵“有根树”表示定义数组set1.nseti=i,则i表示本集合，并是集合对应树的根seti=j,ji,则j是i的父节点.,并查集,find2(x)r=x;while(setr!=r)r=setr;returnr;,merge2(a,b)if(ab)setb=a;elseseta=b;,(1),最坏情况(N)一般情况是?,并查集,性能有本质改进?,如何避免最坏情况?,并查集,方法：将深度小的树合并到深度大的树实现：假设两棵树的深度分别为h1和h2,则合并后的树的高度h是:max(h1,h2),ifh1h2.h1+1,ifh1=h2.效果：任意顺序的合并操作以后，包含k个节点的树的最大高度不超过,并查集,merge3(a,b)if(height(a)=height(b)height(a)=height(a)+1;setb=a;elseif(height(a)height(b)seta=b;elsesetb=a;,find2(x)r=x;while(setr!=r)r=setr;returnr;,最坏情况(logN),(1),并查集,思想：每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快（路径压缩）步骤:第一步，找到根结点第二步，修改查找路径上的所有节点，将它们都指向根结点,并查集,find3(x)r=x;while(setrr)/循环结束，则找到根节点r=setr;i=x;while(ir)/本循环修改查找路径中所有节点j=seti;seti=r;i=j;,并查集,并查集,最小生成树红色字体的两个函数：intfindroot(intp)/找父亲if(fatherp!=p)fatherp=findroot(fatherp);returnfatherp;voidunionset(intp,intq)/合并集合fatherq=p;,再一题畅通工程(HDU-1232),题目描述：某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？,题目分析,最赤裸裸的并查集，无话可说,题目分析:,该你们练习了,参考源码(HDU-1232),#includestdio.hintbin1002;intfindx(intx)intr=x;while(binr!=r)r=binr;returnr;voidmerge(intx,inty)intfx,fy;fx=findx(x);fy=findx(y);if(fx!=fy)binfx=fy;,intmain()intn,m,i,x,y,count;while(scanf(%d,Anyquestion?,相关练习,题目：HDU-1558SegmentsetHDU-1811RankofTetrisHDU-1829ABugsLifeHDU-1198FarmIrrigation,最短路径SPFA,求单源最短路的SPFA算法的全称是：ShortestPathFasterAlgorithm。SPFA算法是西南交通大学段凡丁于1994年发表的.从名字我们就可以看出，这种算法在效率上一定有过人之处。,最短路径SPFA,很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。简洁起见，我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。,最短路径SPFA,我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是松弛：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。,最短路径SPFA,定理:只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值dv变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕）,最短路径SPFA,实现方法：建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空,最短路径SPFA,期望的时间复杂度O(ke)，其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。判断有无负环：如果某个点进入队列的次数超过N次则存在负环(存在负环则无最短路径,如果有负环则会无限松弛,而一个带n个点的图至多松弛n-1次),最短路径SPFA,例题HDU2544输入包括多组数据。每组数据第一行是两个整数N、M（N=100，M=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1=A,B=N,1=C=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。输入保证至少存在1条商店到赛场的路线。,最短路径SPFA,对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间样例输入：211233312523531200样例输出：32,最短路径SPFA,我们根据上面的思想一步步来实现：constintM=105;constintoo=100000000;structnodeintto,next,cap;edgeM*100;inthead2*M,QM*M,mark2*M;intcost2*M;intn,e,src,tot;,最短路径SPFA,voidadd(inta,intb,intc)edgetot.to=b,edgetot.cap=c,edgetot.next=heada,heada=tot+;/临界表，添加边,最短路径SPFA,SPFA函数前半部分voidspfa()for(inti=1;i=n;i+)costi=oo;marki=0;costsrc=0;marksrc=1;intl=0,h=0,k,y;Ql+=src;,最短路径SPFA,SPFA后半部分while(hcostk+edgei.cap)costy=costk+edgei.cap;if(!marky)/