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

最小生成树 并查集 最短路,罗方炜 ,最小生成树,问题描述：某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。,最小生成树,输入：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。 输出：对每个测试用例，在1行里输出最小的公路总长度。,最小生成树,样例输入： 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0 样例输出： 3 5,最小生成树,最小生成树：在一个具有几个顶点的连通图G中，如果存在子图G包含G中所有顶点和一部分边，且不形成回路，则称G为图G的生成树，代价最小生成树则称为最小生成树。简称MST。,最小生成树,一般有两种算法：Prim和Kruskal算法 今天主要讲Kruskal算法，适用本题，给出的边数，复杂度elong(e) (其中e表示变数),最小生成树,算法粗略描述：假设 WN=(V,E) 是一个含有 n 个顶点的连通网，先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。,最小生成树,做法: 定义结点： #define M 10005 struct node int x,y,w; /表示x到y需要花费w eM; int n,m,fatherM; /n定点数量，m边数量，fatherM,每个定点所属集合,最小生成树,int kruskal() int res=0,k=1,j=0; for(int i=1; i=m; i+) fatheri=i; /初始化集合数组 while(kn ,最小生成树,int main() while(scanf(“%d“, ,最小生成树,整体思想已经完成，但是可以看到第二部分红色字体标出的代码： sn1=findroot(m1), sn2=findroot(m2); unionset(sn1,sn2); 这部分涉及到了集合操作，也就是我们马上要讲的并查集,并查集,英文：Disjoint Set，即“不相交集合” 将编号分别为1N的N个对象划分为不相交集合， 在每个集合中，选择其中某个元素代表所在集合。 常见两种操作： 合并两个集合 查找某元素属于哪个集合,所以，也称为“并查集”,并查集,用编号最小的元素标记所在集合； 定义一个数组 set1n ，其中seti 表示元素i 所在的集合；,i,Set(i),不相交集合： 1,3,7, 4, 2,5,9,10, 6,8,并查集,find1(x) return setx; ,Merge1(a,b) i = min(a,b); j = max(a,b); for (k=1; k=N; k+) if (setk = j) setk = i; ,(1),(N),并查集,对于“合并操作”，必须搜索全部元素！,树结构如何？,并查集,每个集合用一棵“有根树”表示 定义数组 set1n seti = i , 则i表示本集合，并是集合对应树的根 seti = j, ji, 则 j 是 i 的父节点.,并查集,find2(x) r = x; while (setr != r) r = setr; return r; ,merge2(a, b) if (ab) setb = a; else seta = b; ,(1),最坏情况(N) 一般情况是?,并查集,性能有本质改进?,如何避免最坏情况?,并查集,方法：将深度小的树合并到深度大的树 实现：假设两棵树的深度分别为h1和h2, 则合并后的树的高度h是: max(h1,h2), if h1h2. h1+1, if h1=h2. 效果：任意顺序的合并操作以后，包含k个节点的树的最大高度不超过,并查集,merge3(a,b) if (height(a) = height(b) height(a) = height(a) + 1; setb = a; else if (height(a) height(b) seta = b; else setb = a; ,find2(x) r = x; while (setr != r) r = setr; return r; ,最坏情况(log N),(1),并查集,思想：每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快（路径压缩） 步骤: 第一步，找到根结点 第二步，修改查找路径上的所有节点，将它们都指向根结点,并查集,find3(x) r = x; while (setr r) /循环结束，则找到根节点 r = setr; i = x; while (i r) /本循环修改查找路径中所有节点 j = seti; seti = r; i = j; ,并查集,并查集,最小生成树红色字体的两个函数： int findroot(int p) /找父亲 if(fatherp!=p) fatherp=findroot(fatherp); return fatherp; void unionset(int p,int q) /合并集合 fatherq=p; ,再一题畅通工程(HDU-1232),题目描述： 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？,题目分析,最赤裸裸的并查集，无话可说,题目分析:,该你们练习了,参考源码(HDU-1232),#include “stdio.h“ int bin1002; int findx(int x) int r=x; while(binr !=r) r=binr; return r; void merge(int x,int y) int fx,fy; fx = findx(x); fy = findx(y); if(fx != fy) binfx = fy; ,int main() int n,m,i,x,y,count; while(scanf(“%d“, ,Any question?,相关练习,题目： HDU-1558 Segment set HDU-1811 Rank of Tetris HDU-1829 A Bugs Life HDU-1198 Farm Irrigation,最短路径SPFA,求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。 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,例题HDU 2544 输入包括多组数据。每组数据第一行是两个整数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,对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间 样例输入：2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0 样例输出：3 2,最短路径SPFA,我们根据上面的思想一步步来实现： const int M=105; const int oo=100000000; struct node int to,next,cap; edgeM*100; int head2*M, QM*M, mark2*M; int cost2*M; int n,e,src,tot;,最短路径SPFA,void add(int a, int b, int c) edgetot.to=b, edgetot.cap=c, edgetot.next=heada, heada=tot+; /临界表，添加边,最短路径SPFA,SPFA函数前半部分 void spfa() for(int i=1; i=n; i+) costi=oo; marki=0; costsrc=0; marksrc=1; int l=0,h=0,k,y; Ql+=src;,最短路径SPFA,SPFA后半部分 while(hcostk+edgei.cap) costy=costk+edgei.cap; if(!marky) /避