最小生成树最小生成树 并查集并查集 最短路最短路罗方炜小生成树并查集最短路最小生成树最小生成树问题描述：问题描述：某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 小生成树并查集最短路最小生成树最小生成树输入：输入：测试输入包含若干测试用例。每个测试用例的第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 样例输出：样例输出：35小生成树并查集最短路最小生成树最小生成树最小生成树：最小生成树：在一个具有几个顶点的连通图G中，如果存在子图G包含G中所有顶点和一部分边，且不形成回路，则称G为图G的生成树，代价最小生成树则称为最小生成树。简称MST。小生成树并查集最短路最小生成树最小生成树一般有两种算法：一般有两种算法：Prim和Kruskal算法 今天主要讲Kruskal算法，适用本题，给出的边数，复杂度elong(e) (其中e表示变数)小生成树并查集最短路最小生成树最小生成树算法粗略描述：算法粗略描述：假设 WN=(V,E) 是一个含有 n 个顶点的连通网，先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集从网的边集 E 中选取一条权值最小的边中选取一条权值最小的边，若该条边的两个顶点分属不同的树分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止条边为止。小生成树并查集最短路最小生成树最小生成树做法做法:定义结点：定义结点：#define M 10005struct nodeint x,y,w; /表示x到y需要花费weM;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 & jm) /需要n-1条边int m1=ej.x, m2=ej.y;int sn1=findroot(m1), sn2=findroot(m2);If(sn1!=sn2) res+=ej.w; k+; /生成数+1unionset(sn1,sn2);j+;if(k!=n) res=-1; /不可能的情况 ,产生不了最小生成树return res;小生成树并查集最短路最小生成树最小生成树int main() while(scanf(%d,&n) & n) m=n*(n-1)/2; for(int i=0; im; i+) scanf(%d%d%d,&ei.x,&ei.y,&ei.w); sort(e,e+m,cmp); /排序按边权w值从小到大排序 printf(%dn,kruskal(); 小生成树并查集最短路最小生成树最小生成树整体思想已经完成，但是可以看到第二部分红色字体标出的代码：sn1=findroot(m1), sn2=findroot(m2);unionset(sn1,sn2);这部分涉及到了集合操作，也就是我这部分涉及到了集合操作，也就是我们马上要讲的们马上要讲的并查集并查集小生成树并查集最短路并查集并查集英文：Disjoint Set，即“不相交集合”将编号分别为1N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合。常见两种操作：n合并并两个集合n查查找某元素属于哪个集合所以，也称为“并查集”小生成树并查集最短路并查集并查集n用编号最小的元素标记所在集合；n定义一个数组 set1.n ，其中seti 表示元素i 所在的集合；123456789101214261622iSet(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)小生成树并查集最短路并查集并查集n对于“合并操作”，必须搜索全部元素！n树结构如何？小生成树并查集最短路并查集并查集n每个集合用一棵“有根树”表示n定义数组 set1.nnseti = i , 则i表示本集合，并是集合对应树的根nseti = j, ji, 则 j 是 i 的父节点. 123456789101232134334iSet(i)15247103689小生成树并查集最短路并查集并查集find2(x) r = x; while (setr != r) r = setr; return r;merge2(a, b) if (ab) setb = a; else seta = b;(1)最坏情况(N)一般情况是?小生成树并查集最短路并查集并查集n性能有本质改进?n如何避免最坏情况?小生成树并查集最短路并查集并查集n方法：将深度小的树合并到深度大的树n实现：假设两棵树的深度分别为h1和h2, 则合并后的树的高度h是:nmax(h1,h2), if h1h2.nh1+1, if h1=h2.n效果：任意顺序的合并操作以后，包含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)小生成树并查集最短路并查集并查集n思想：每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快（路径压缩路径压缩）n步骤:n第一步，找到根结点n第二步，修改查找路径上的所有节点，将它们都指向根结点小生成树并查集最短路并查集并查集nfind3(x)nn r = x;n while (setr r) /循环结束，则找到根节点n r = setr; n i = x;n while (i r) /本循环修改查找路径中所有节点n n j = seti;n seti = r;n i = j;n 小生成树并查集最短路并查集并查集91081220211646111641111012982021 16小生成树并查集最短路并查集并查集n最小生成树红色字体的两个函数：nint findroot(int p) /找父亲if(fatherp!=p) fatherp=findroot(fatherp); return fatherp;nvoid unionset(int p,int q) /合并集合fatherq=p;小生成树并查集最短路再一题再一题畅通工程畅通工程(HDU-1232)n题目描述：题目描述：某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？ 小生成树并查集最短路题目分析n最赤裸裸的并查集，无话可说小生成树并查集最短路题目分析:n该你们练该你们练习了习了小生成树并查集最短路参考源码(HDU-1232)n#include stdio.hnint bin1002;nint findx(int x)nn int r=x;n while(binr !=r)n r=binr;n return r;nnvoid merge(int x,int y)nn int fx,fy;n fx = findx(x);n fy = findx(y);n if(fx != fy)n binfx = fy;nnint main()nn int n,m,i,x,y,count;n while(scanf(%d,&n),n)n n for(i=1;i0;m-)n n scanf(%d %d,&x,&y);n merge(x,y);n n for(count=-1, i=1;i=n;i+)n if(bini = i)n count +;n printf(%dn,count);n n小生成树并查集最短路Any question?小生成树并查集最短路相关练习题目：题目：nHDU-1558Segment set nHDU-1811Rank of Tetris nHDU-1829A Bugs Life nHDU-1198Farm Irrigation 小生成树并查集最短路最短路径SPFAn求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。nSPFA算法是西南交通大学段凡丁于1994年发表的.n从名字我们就可以看出，这种算法在效率上一定有过人之处。小生成树并查集最短路最短路径SPFAn很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。n简洁起见，我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。小生成树并查集最短路最短路径SPFAn我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是松弛：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。 小生成树并查集最短路最短路径SPFAn定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。n证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值dv变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕）小生成树并查集最短路最短路径SPFAn实现方法：建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空小生成树并查集最短路最短路径SPFAn期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。 n判断有无负环：如果某个点进入队列的次数超过N次则存在负环 ( 存在负环则无最短路径,如果有负环则会无限松弛,而一个带n个点的图至多松弛n-1次) 小生成树并查集最短路最短路径SPFAn例题HDU 2544n输入包括多组数据。每组数据第一行是两个整数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条商店到赛场的路线。 小生成树并查集最短路最短路径SPFAn对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间 n样例输入：2 1n1 2 3 n3 3 n1 2 5 2 3 5 3 1 2 n0 0 n样例输出：3 2小生成树并查集最短路最短路径SPFAn我们根据上面的思想一步步来实现：nconst int M=105;nconst int oo=100000000;nstruct node int to,next,cap;n edgeM*100;nint head2*M, QM*M, mark2*M;nint cost2*M;nint n,e,src,tot;小生成树并查集最短路最短路径SPFAnvoid add(int a, int b, int c) edgetot.to=b, edgetot.cap=c, edgetot.next=heada, heada=tot+;n /临界表，添加边小生成树并查集最短路最短路径SPFAnSPFA函数前半部分nvoid 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;小生成树并查集最短路最短路径SPFAnSPFA后半部分n while(hcostk+edgei.cap) n costy=costk+edgei.cap;n if(!marky) /避免重复入列 n Ql+=y;n marky=1;n n n n n小生成树并查集最短路最短路径SPFAn主函数nint main()n while(scanf(%d%d,&n,&e) != EOF)nif(n=0 & e=0) break;n tot=0;n for(int i=1; i=n; i+) headi=-1;n for(int i=1; i=e; i+)n int u,w,v;n scanf(%d%d%d,&u,&w,&v);n add(u,w,v); add(w,u,v); n n int st=1,ed=n;n src=st;n spfa();n printf(%dn,costed);n n小生成树并查集最短路最短路径SPFAn需要注意的地方：1、是双向边2、主函数里对临界表的初始化3、SPFA函数里的标记数组mark4、队列的使用，空间大小小生成树并查集最短路最短路径SPFAn其他相关练习：nHDU 3790nPKU 1151nPKU 2387最短路的算法有很多，SPFA是很高效的一种，但希望大家对一般算法也去了解下，对比中发现优劣小生成树并查集最短路大家休息了，下课大家休息了，下课Thank You 小生成树并查集最短路