图论算法总结及图论建模.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑文本,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑文本,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑文本,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑文本,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑文本,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑文本,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑文本,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑文本,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑文本,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑文本,第二级,第三级,第四级,第五级,*,*,图论,算法总结,图的基本概念,图的基本概念,二元组 G(V,E)称为图(graph)。V为结点(node)或顶点(vertex)集。E为图中结点之间的边的集合。,点，用数字,0n-1,表示,点对(u,v)称为边(edge)或称弧(arc),对于边(u,v)E,-u,和,v,邻接,(adjacent),-e,和,u,、,v,关联,(incident),子图,(,subgraph,):,边的子集和相关联的点集,图的基本概念,有向图：边都是单向(unidirectional)的,因此边(u,v)是有序数对.有时用弧(arc)专指有向边,带权图：可以给边加权(weight),成为带权图,或加权图(weighted graph).权通常代表费用、距离等,可以是正数,也可以是负数,稠密性：边和V(V-1)/2相比非常少的称为稀疏图(sparse graph),它的补图为稠密图(dense graph),路径和圈,一条路径(path)是一个结点序列,路上的相邻结点在图上是邻接的,如果结点和边都不重复出现,则称为简单路径(simple path).如果除了起点和终点相同外没有重复顶点和边,称为圈(cycle).,不相交路(disjoint path)表示没有除了起点和终点没有公共点的路.更严格地,-,任意点都不相同的叫严格不相交路,(vertex-disjoint path),-,同理定义边不相交,(edge-disjoint path),路,注意:汉语中圈和环经常混用(包括一些固定术语).由于一般不讨论自环(self-loop),所以以后假设二者等价而不会引起混淆,连通性,如果任意两点都有路径,则称图是连通(connected)的,否则称图是非连通的.,非连通图有多个连通分量(connected component,cc),每个连通分量是一个极大连通子图(maximal connected subgraph),完全图和补图,完全图:N个顶点的图，有N(N-1)/2个节点,对于(u,v),若邻接则改为非邻接,若非邻接则改为邻接,得到的图为原图的补图,完全图=原图补图,团：完全子图,生成树,树：N个点，N-1条边的连通图（无环连通图）,生成树:包含某图G所有点的树,一个图G是树当且仅当以下任意一个条件成立,G,有,V-1,条边,无圈,G,有,V-1,条边,连通,任意两点只有唯一的简单路径,G,连通,但任意删除一条边后不连通,图例,图的表示方法,介绍两种图的表示方法：邻接矩阵与邻接表,V*V的二维数组A，Aij=0,若(i,j)不相连，Aij=1,若(i,j)相连,图,1,图,1,的邻接矩阵表示,邻接矩阵,无向图的邻接矩阵是对称的,优点：查找/删除某条边是O(1)的,缺点,遍历某一点的邻居是,O(V),的,空间复杂度很大，,O(V*V),每个结点的邻居形成一个链表,邻接表,图,2,图,2,的邻接表表示,优点,快速遍历某点所有邻居,占用存储空间小，是O（边数）的，在稀疏图上的效率远胜邻接表,缺点：查找/删除边不是常数时间,邻接表,一、宽度优先遍历,(BFS),二、深度优先遍历,(DFS),图的遍历算法,给定图G和一个源点s,宽度优先遍历按照从近到远的顺序考虑各条边.算法求出从s到各点的距离,宽度优先的过程对结点着色.,白色,:,没有考虑过的点,黑色,:,已经完全考虑过的点,灰色,:,发现过,但没有处理过,是遍历边界,依次处理每个灰色结点u,对于邻接边(u,v),把v着成灰色并加入树中,在树中u是v的父亲(parent)或称前驱(predecessor).距离dv=du+1,整棵树的根为s,宽度优先遍历,(BFS),题目大意：,给出N*M个格子，给出K个已经被淹没的格子，其他格子都是干的，求最大的湖的面积（一个格子的面积视为1），如果两个湿的格子四联通（上下左右），则视为这两个格子同属于一个湖,输入格式：,第一行N，M，K,接下来K个格子的坐标,Avoid The Lakes,（,NOI,题库,2405,）,Input,3 4 5,3 2,2 2,3 1,2 3 1 1,Output,4,样例解释,#.,.#.,#.,新发现的结点先扩展,得到的可能不是一棵树而是森林,即深度优先森林(Depth-first forest),特别之处:引入时间戳(timestamp),发现时间dv:变灰的时间,结束时间fv:变黑的时间,1=dv fv=2|V|,深度优先遍历,(DFS),初始化:time为0,所有点为白色,dfs森林为空,对每个白色点u执行一次DFS-VISIT(u),时间复杂度为O(n+m),深度优先遍历,(DFS),括号结构性质,对于任意结点对(u,v),考虑区间du,fu和dv,fv,以下三个性质恰有一个成立:,完全分离,u,的区间完全包含在,v,的区间内,则在,dfs,树上,u,是,v,的后代,v,的区间完全包含在,u,的区间内,则在,dfs,树上,v,是,u,的后代,DFS,树的性质,定理(嵌套区间定理):,在DFS森林中v是u的后代当且仅当dudvfvfu,即区间包含关系.由区间性质立即得到.,DFS,树的性质,一条边(u,v)可以按如下规则分类,树边,(Tree Edges,T):v,通过边,(u,v),发现,后向边,(Back Edges,B):u,是,v,的后代,前向边,(Forward Edges,F):v,是,u,的后代,交叉边,(Cross Edges,C):,其他边，可以连接同一个,DFS,树中没有后代关系的两个结点,也可以连接不同,DFS,树中的结点,判断后代关系可以借助定理1,边的分类,当(u,v)第一次被遍历,考虑v的颜色,白色,(,u,v,),为,T,边,灰色,(,u,v,),为,B,边,(,只有它的祖先是灰色,),黑色,:(,u,v,),为,F,边或,C,边,.,此时需要进一步判断,du,dv,:C,边,(v,早就被发现了,为另一,DFS,树中,),时间复杂度:O(n+m),定理:无向图只有T边和B边(易证),边分类算法,if(,dv,=-1),dfs(v,);/,树边,递归遍历,else if(,fv,=-1),show(“B,”);/,后向边,else if(,dv,du,),show(“F,”);/,前向边,else,show(“C,”);/,交叉边,d和f数组的初值均为-1,方便了判断,实现细节,实现细节,DAG:有向无环图,拓扑顺序：,拓扑排序算法,对图G使用DFS算法,每次把一个结点变黑的同时加到链表首部,AN EXAMPLE,定理1:有向图是DAG当且仅当没有返祖边,如果有返祖边,有环,(,易证,),如果有环,c,考虑其中第一个被发现的结点,v,环中,v,的上一个结点为,u,则沿环的路径,v,u,是白色路径,u,是,v,的后代,因此,(u,v),是返祖边,定理2:该算法正确的得到了一个拓扑顺序的逆序,拓扑排序算法,一、有向图:SCC划分的Kosaraju算法(有兴趣的同学自己看吧),二、有向图:SCC划分的Tarjan算法,三、无向图:割顶和桥的判定,图的连通性算法,有向图中,u可达v不一定意味着v可达u.,相互可达则属于同一个强连通分量,(Strongly Connected Component,SCC),有向图和它的转置的强连通分量相同,所有SCC构成一个DAG,SCC,的概念,Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树,搜索时，把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。,tarjan,算法,(,参考,byvoid,博客,),定义：,DFN(u,),为节点,u,搜索的次序编号,(,时间戳,),Low(u,),为,u,或,u,的子树能够追溯到的最早的栈中节点的次序号,当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。,dfn,与,low,函数,算法伪代码,tarjan(u),DFNu=Lowu=+Index /,为节点,u,设定次序编号和,Low,初值,Stack.push(u)/,将节点,u,压入栈中,for each(u,v)in E /,枚举每一条边,if(v is not visted)/,如果节点,v,未被访问过,tarjan(v)/,继续向下找,Lowu=min(Lowu,Lowv),else if(v in S)/,如果节点,v,还在栈内,Lowu=min(Lowu,DFNv),if(DFNu=Lowu)/,如果节点,u,是强连通分量的根,repeat,v=S.pop /,将,v,退栈，为该强连通分量中一个顶点,print v,until(u=v),算法演示,算法演示,算法演示,算法演示,完整代码,void tarjan(int i),int j;,DFNi=LOWi=+Dindex;,instacki=true;,Stap+Stop=i;,for(edge*e=Vi;e;e=e-next),j=e-t;,if(!DFNj),tarjan(j);,if(LOWjLOWi),LOWi=LOWj;,else if(instackj&DFNjLOWi),LOWi=DFNj;,if(DFNi=LOWi),Bcnt+;,do,j=StapStop-;,instackj=false;,Belongj=Bcnt;,while(j!=i);,void solve(),int i;,Stop=Bcnt=Dindex=0;,memset(DFN,0,sizeof(DFN);,for(i=1;i0,then inc(s2),else begin,for j:=1 to n do,if jdj=i,then inc(s3);,end;,if s2+1=s,then writeln(s3),else writeln(0);,end.,3.,4.,对于无向连通图G,割顶是去掉以后让图不连通的点,桥是去掉以后让图不连通的边,割顶与桥,lowu为u及其的后代所能追溯到的最早(最先被发现)祖先点v的,dfnv,值,类似有向图的计算方式,注意无向图只有T和B边,lowu,=,dfnu,=time+;,for(u,的不等于,u,的邻居,v)/,不考虑自环,if(,prev,=-1)/,白色点,dfs-visit(v,);,if(,lowu,lowv,),lowu,=,lowv,;,else,if(,lowu,dfnv,),lowu,=,dfnv,;,无向图的,LOW,函数,在一棵DFS树中,根root是割顶当且仅当它至少有两个儿子,其他点v是割顶当且仅当它有一个儿子u,从u或者u的后代出发没有指向v祖先(不含v)的B边,则删除v以后u和v的父亲不连通,故为割顶,割顶判定算法:,对于DFS树根,判断度数是否大于1,对于其他点u,如果不是根的直接儿子,且lowu=dfnPu,则它的父亲v=Pu是割点,割顶的判定,Network(POJ 1144),void dfs(int u,int dep),dfnu=lowu=dep;,for(int i=0;i=dfnu)cutu=true;,/,由后继节点搜不到比该点更早的点，则该点是割点,else lowu=min(lowu,dfnv);,题目大意：给定一个无向图，求有多少点是割点,边(u,v)为桥当且仅当它不在任何一个简单回路中,发现T边(u,v)时若发现v和它的后代不存在一条连接u或其祖先的B边,则删除(u,v)后u和v不连通,因此(u,v)为桥,桥的判定算法:发现T边(u,v)时若LOWvdu(注意不能取等号),则(u,v)为桥,桥的判定,Byteotia有n个镇。有的镇被双向的道路连接。每一对镇间最多只有一条直接连接的道路。任意两个镇连通。,每个镇刚好有一个市民。他们为孤独所困。每个居民都想看看其他所有居民（去他所在的地方），而且刚好做一次。所以刚好发生了n*(n-1)次访问。不幸的是，一些程序员正在罢工，为了使软件的销售量提高。作为抗议活动的一部分，程序员想把Byteotia的一条道路关闭，阻止通过这条道路。他们正在辩论选择哪一条道路会使得后果最严重。（后果最严重即删去这条道路后访问次数最少）,例题,例题,如图，若删去,D,E,之间的边，则会减少,16,次访问，若删去,G,H,之间的，会减少,7,次访问。若删除其它边，则不会减少访问次数。,A,C,B,G,D,F,E,H,应该删除哪些边？,很显然，只有删除桥才会减少访问次数，删去其它的边，图依然保持连通。,因此，首先应该求出所有的桥。,例题,然后我们分别考虑每个桥的情况，删去这条边，会导致把图分成2个部分，而这两个部分是不连通的。考虑损失掉的访问，其实就是跨越这两个部分的访问，即|S1|*|S2|次访问，|S1|,|S2|是两个部分的大小。,由此，大致的算法就形成了，枚举每一条边，然后计算损失的访问，最后输出答案即可。,例题,procedure tarjan(u:longint);,var,p:node;,v:longint;,begin,fu:=false;inc(time);,lowu:=time;dfnu:=time;p:=headu;,while p.keyu do,begin,v:=p.key;,if fv,then begin,fav:=u;,tarjan(v);,lowu:=min(lowu,lowv);,if lowvdfnu,then begin,inc(s);,x1s:=u;,y1s:=v;,end;,end,else if fauv then lowu:=min(lowu,dfnv);,p:=p.next;,end;,end;,function dfs(u:longint):longint;,begin,fu:=false;p:=headu;,while p.keyu do,begin,v:=p.key;,if fv,then begin,treeu:=treeu+dfs(v);fav:=u;,end;,p:=p.next;,end;,inc(treeu);,exit(treeu);,end;,1.,2.,function count(x:longint):longint;,begin,while fax0 do,x:=fax;,count:=treex;,end;,begin,read(n);,for i:=1 to n do,begin,new(headi);,headi.key:=i;headi.next:=nil;,end;,read(m);,for i:=1 to m do,begin,read(x,y);,new(p);p.next:=headx;p.key:=y;,headx:=p;new(p);,p.next:=heady;p.key:=x;heady:=p;,end;,fillchar(f,sizeof(f),true);,s:=0;,for i:=1 to n do,begin,if fi,then begin,time:=0;,tarjan(i);,end;,end;,fillchar(f,sizeof(f),true);,fillchar(tree,sizeof(tree),0);,fillchar(fa,sizeof(fa),0);,for i:=1 to n do,begin,if fi,then temp:=dfs(i);,end;,max:=0;,3.,4.,for i:=1 to s do,begin,c1:=treex1i;,c2:=treey1i;,if c1c2,then c3:=(count(c1)-treey1i)*treey1i,else c3:=(count(c2)-treex1i)*treex1i;,if c3max,then begin,max:=c3;,x2:=x1i;,y2:=y1i;,end;,end;,writeln(max,x2,y2);,end.,5.,给定一张连通图G（V,E）(V=5,000，E=10,000),询问至少要添加多少条边，使得，任意两点间至少有2条路径可达？,Redundant Paths(POJ 3177),Redundant Paths(POJ 3177),if dfnu=lowu,then begin,inc(s);,while stacktopu do,begin,instackstacktop:=false,;,hashstacktop:=s;,stacktop:=0;dec(top);,end;,instackstacktop:=false;,hashstacktop:=s;,stacktop:=0;dec(top);,end;,end;,1.,2.,fillchar(map,sizeof(map),true);,fillchar(s2,sizeof(s2),0);,for i:=1 to m do,begin,if(hashxihashyi)and,(maphashxi,hashyi),then begin,maphashxi,hashyi:=false;,maphashyi,hashxi:=false;,inc(s2hashxi);inc(s2hashyi);,end;,end;,s1:=0;,for i:=1 to s do,if s2i=1,then inc(s1);,writeln(s1+1)div 2);,end.,3.,4.,图的最短路问题,SSSP,的,Spfa,算法,SSSP,的,Dijkstra,算法,差分约束系统,Floyd-warshall,算法,给定带权图和一个起点s,求s到所有点的最短路(边权和最小的路径),最短路有环吗,正环,:,何必呢,删除环则得到更短路,负环,:,无最短路,因为可以沿负环兜圈子,单源最短路问题,(Single Source Shortest Path),最优性原理:若最短路u,v经过中间结点w,则uw和wv的路径分别是u到w和w到v的最短路,意义:贪心、动态规划,最优性原理,最短路的表示,s,到所有点的最短路不需要分别表示,最短路树,:,到每个点都沿着树上的唯一路径走,实际代码,:,记录每个点的父亲,predu,即可,输出最短路,:,从终点沿着,predu,递推回起点,最短路的表示,松弛（RELAX）操作,一条边,(,u,v,),被称为紧的,(tense),如果,dist(u)+w(u,v,)3-4-5,。注意点,2,不能在答案路径中，因为点,2,连了一条边到点,6,，而点,6,不与终点,5,连通。,大致思路：,因为路径上的所有点的出边所指向的点都直接或间接与终点连通，所以我们不妨把所有的边反向，然后求t到s的最短路径,大致证明：,先将所有边按照读入顺序标号,所有满足条件1的从s到t路径，在边都反向的情况下，对应一条t到s的路径，并且满足一一对应（因为路径上边的标号都相同）,Tips：这里的最短路可以BFS求得（因为路径长度都是1）,NOIP2014Day2T2,寻找道路,begin,/,主程序,read(n,m1);,for i:=1 to n do,begin,new(headi);headi:=nil;new(head1i);head1i:=nil;,end;,for i:=1 to m1 do,read(xi,yi);,read(a,b);,sort(1,m1);,m:=0;fillchar(f,sizeof(f),true);x1:=0;y1:=0;,fillchar(s,sizeof(s),0);,for i:=1 to m1 do,begin,if xi=yi,then fxi:=false,else begin,if(xi=x1)and(yi=y1)then continue;,inc(sxi);inc(m);,x1:=xi;y1:=yi;,new(p);p.key:=y1;p.next:=headx1;headx1:=p;,new(p);p.key:=x1;p.next:=head1y1;head1y1:=p;,end;,end;,procedure dfs1(u:longint);,/,子程序,var,p:node;,v:longint;,begin,fu:=false;,p:=head1u;,while pnil do,begin,v:=p.key;,if fv,then begin,inc(s1v);,fv:=false;,dfs1(v);,end,else inc(s1v);,p:=p.next;,end;,end;,1.,2.,fillchar(s1,sizeof(s1),0);,fillchar(f,sizeof(f),true);,dfs1(b);,fillchar(al,sizeof(al),true);,for i:=1 to n do,begin,if i=b,then continue;,if sis1i,then ali:=false;,end;,find:=false;,head2:=0;,tail:=1;,fillchar(q,sizeof(q),0);,q1.key:=a;,q1.dist:=0;,fillchar(f,sizeof(f),true);,fa:=false;,while head2tail do,begin,inc(head2);u:=qhead2.key;p:=headu;,while pnil do,begin,v:=p.key;,if(fv)and(alv),then begin,fv:=false;inc(tail);,qtail.key:=v;qtail.dist:=qhead2.dist+1;,if v=b,then begin,writeln(qtail.dist);,find:=true;break;,end;,end;,p:=p.next;,end;,if find,then break;,if find=false,then writeln(-1);,end.,3.,4.,线性规划(linear programming,LP):给m*n矩阵A、m维向量b和n维向量c,求出x为向量使得Ax=b,且sumcixi最小,可行性问题(feasibility problem):只需要任意找出一组满足Ax=b的解向量x,差分约束系统(system of difference constraints):A的每行恰好一个1和一个-1,其他元素都是0.相当于关于n个变量的m个差分约束,每个约束都形如xj-xi=bk,其中1=i,j=n,1=k=m.,差分约束系统,左边的可行性问题等价于右边的差分约束系统,差分约束系统,约束图:结点是变量,一个约束对应一条弧,若有弧(u,v),则得到xu后,有xv max,then max:=xi;,if yimax,then max:=yi;,end;,n:=max;,for i:=0 to n do,begin,new(headi);,headi:=nil;,end;,for i:=0 to n-1 do,begin,new(p);p.dis:=1;p.key:=i+1;,p.next:=headi;headi:=p;,end;,for i:=n downto 1 do,begin,new(p);,p.dis:=0;p.key:=i-1;p.next:=headi;headi:=p;,end;,for i:=1 to m do,begin,xi:=xi-1;,new(p);p.dis:=-zi;p.key:=xi;p.next:=headyi;,headyi:=p;,end;k:=n;,for i:=0 to n do,begin,disti:=huge;,end;,tail:=1;,head1:=0;,q1:=k;,fillchar(f,sizeof(f),true);,distk:=0;,fk:=false;,1.,2.,while head1tail do,begin,inc(head1);,u:=qhead1;,p:=headu;,while pnil do,begin,v:=p.key;,if distu+p.dis2,就是说至除了出发点以外至少要经过,2,个其他不同的景区，而且不能重复经过同一个景区。现在,8600,需要你帮他找一条这样的路线，并且花费越少越好。,HDU1599,：,find the mincost route,Input,：第一行是,2,个整数,N,和,M,（,N=100,M=1000),，代表景区的个数和道路的条数。接下来的,M,行里，每行包括,3,个整数,a,b,c,。代表,a,和,b,之间有一条通路，并且需要花费,c,元,(c k-v-(x1-x2-,xm,)-,u(u,与,k,、,k,与,v,都是直接相连的,),，其中,v-(x1-x2-,xm,)-u,是指,v,到,u,不经过,k,的一种路径。,HDU1599,：,find the mincost route,在,u,，,k,，,v,确定的情况下，要使环权值最小，则要求,(x1-x2-,xm,)-u,路径权值最小即要求其为,v,到,u,不经过,k,的最短路径，则这个经过,u,，,k,，,v,的环的最短路径就是：,v,到,u,不包含,k,的最短距离,+dist0,，,u,，,k+dist0,，,k,，,v,。我们用,Floyd,只能求出任意,2,点间满足中间结点均属于集合,1,，,2,，,k,的最短路径，可是我们如何求出,v,到,u,不包含,k,的最短距离呢,?,HDU1599,：,find the mincost route,现在我们给,k,加一个限制条件：,k,为当前环中的序号最大的节点,(,简称最大点,),。因为,k,是最大点，所以当前环中没有任何一个点,k,，即所有点都,(x1-x2-.,xm,)-u,属于当前环，所以,x1,，,x2,，,xm,k,，即,x1,，,x2,xm,k-1,。这样，,v,到,u,的最短距离就可以表示成,distk-1,u,v,。,distk-1,v,u,表示的是从,v,到,u,且满足所有中间结点均属于集合,1,，,2,，,k-1,的一条最短路径的权。接下来，我们就可以求出,v,到,u,不包含,k,的最短距离了。这里只是要求不包含,k,，而上述方法用的是,distk-1,，,v,，,u,，求出的路径永远不会包含,k+1,，,k+2,，,HDU1599,：,find the mincost route,万一所求的最小环中包含,k+1,，,k+2,，怎么办呢,?,的确，如果最小环中包含比,k,大的节点，在当前,u,k,v,所求出的环显然不是那个最小环。然而我们知道，这个最小环中必定有一个最大点,k0,，也就是说，虽然当前,k,没有求出我们所需要的最小环，但是当我们从,k,做到,k0,的时候，这个环上的所有点都小于,k0,了也就是说在,k=k0,时一定能求出这个最小环。,HDU1599,：,find the mincost route,我们用一个实例来说明：假设最小环为,1345621,。的确，在,u=1,，,v=4,，,k=3,时，,k6,，,dist3,，,4,，,1,的确求出的不是,45621,这个环，但是，当,u=4,，,v=6,，,k=5,或,u=5,，,v=2,，,k=6,时，,distk,，,v,，,u,表示的都是这条最短路径,.,所以我们在,Floyd,以后，只要枚举,u,v,，,k,三个变量即可求出最小环。时间复杂度为,O(n3),。我们可以发现，,Floyd,和最后枚举,u,，,v,，,k,三个变量求最小环的过程都是,u,v,k,三个变量，所以我们可以将其合并。这样，我们在,k,变量变化的同时，也就是进行,Floyd,算法的同时，寻找最大点为,k,的最小环。,HDU1599,：,find the mincost route,最小生成树（,MST,Minimal Spanning Tree,）,PRIM,算法,并查集,KRUSKAL,算法,给定图G,求连接每个点的连通图（一定是树）,权和尽量小,最小生成树,假设选取若干条边，使得当前的图被分成了若干个连通分量,无用边：边的两个端点属于同一个连通分量，但这条边不属于任意一个连通分量,安全边：从它出去(即恰好有一个端点在此分量内)的最小边,不同的分量可以有相同的安全边,结论:MST含有所有安全边,不含无用边.,最小生成树思想,结论:MST含有所有安全边,不含无用边.,证明,假设有一个分量,(,黄色,),它的安全边,e,不在,T,内,.,则,u,到,v,有唯一路径,它经过,e,它恰好有一个端点在黄色分量中,.,由于,e,是安全边,w(e,),w(e,),用,e,替换,e,得到更小的,T,矛盾,加入无用边将形成环,最小生成树思想,只关心一棵树T,每次加入T的安全边,用堆保存到每个顶点(而非边)的安全边,Insert/ExtractMin调用V次,DecreaseKey调用E次,二叉堆:O(E+V)logV),Fibonacci堆:O(E+VlogV),PRIM,算法,PRIM,算法,将编号分别为1N的N个对象划分为不相交集合,在每个集合中，选择其中某个元素代表所在集合,常见两种操作：,合并两个集合,查找某元素属于哪个集合,并查集,Disjoint Set,每个集合用一棵“有根树”表示,定义数组fa1.n,fai,=i,，则,i,表示本集合，并是集合对应树的树根,seti,=j,ji,则,j,是,i,的父节点,并查集,Disjoint Set,1,2,3,4,5,6,7,8,9,10,1,2,3,2,1,3,4,3,3,4,i,Set(i),1,5,2,4,7,10,3,6,8,9,查询x所在集合根节点合并集合a,b,并查集,Disjoint Set,find(x),while(fax!=x)x=fax;,return x;,最坏情况,(log N),merge(a,b),if(height(a)=height(b),height(a)=height(a)+1;,fab=a;,else if(height(a)height(b)faa=b;,else fab=a;,(1),思想：每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快,步骤:,第一步，找到根结点,第二步，修改查找路径上的所有节点，将它们都指向根结点,路径压缩优化,find(x),while(x!=fax)fax=find(fax);,return fax;,路径压缩优化,9,10,8,12,20,21,16,4,6,11,1,6,4,11,1,10,12,9,8,20,21,16,Kruskal,1956年提出,把边从小到大排序,每次填加一个安全边,如何知道边是否安全?并查集,每次约O(1),总O(ElogE+E,(V),Kruskal,算法,在二维平面上有N个村庄，坐标（xi,yi）给定,为其中的S个村庄配备卫星通信设备，使得配备了卫星通信的村庄间互相都能沟通,为每个村庄配备一个无线电，能使其能与距离不超过D的村庄沟通,求一种卫星通信设备的分配方案，使得D最小，并且满足任意两个村庄之间能沟通，直接或间接,Arctic Network POJ2349,Sample Input,Sample Output,212.13,Arctic Network POJ2349,假设d 已知，把所有铺设线路的村庄连接起来，构成一个图。需要卫星设备的台数就是图的连通支的个数。,d越小，连通支就可能越多。,那么，只需找到一个最小的d，使得连通支的个数小于等于卫星设备的数目。,Arctic Network POJ2349,把整个问题看做一个完全图，村庄就是点，图上两点之间的边的权值，就是两个村庄的直线距离。,只需在该图上求最小生成树，d 的最小值即为第K 长边！,因为：最小生成树中的最长k-1条长边都去掉后，正好将原树分成了k 个连通分支，在每个连通分支上摆一个卫星设备即可,Arctic Network POJ2349,为什么d不可能比第k长边更小？,假设最小生成树,T,上，第,k,长边连接的点是,a,b,，那么将边,去掉后，树就分成了两个部分,T1,和,T2,要使,T1,和,T2,能够通讯，必须在,T1,中找一点,p,和,T2,中的点,q,相连，若边,的长度小于,，则在,T,上用,替换,就能得到更小的生成树，矛盾。因此找不到长度小于,的,。,对任何比第,k,长边短的边,e,，同理也不可能找到替代,e,的边。,因此,d,不可能更小了,Arctic Network POJ2349,最小生成树可能不止一棵，为什么第k长边长度一定相同？因为有以下结论：,一个图的两棵最小生成树，边的权值序列排序后结果相同,证明：假设某个最小生成树T1的边权从小到大排序后的序列为:a1,a2.an,某个最小生成树T2的边权从小到大排序后的序列为:b1,b2bn,两者若不同，则必然存在一个最小的i,使得ai bi,假设T2中有m条边的权为bi，那么，T1中最多只有m-1条边的权和bi相同。,Arctic Network POJ2349,但是对于T2中任何一条不在T1中的权为bi的边，如果将其从T2去掉，则T2被分成A,B两个部分。那么在T1中连接A,B这两个部分的边，必然权值是等于bi的，否则经过替换，要么T1的权值可以变得更小，要么T2的权值可以变得更小，这和T1,T2是最小生成树矛盾。对T2中每个权值为bi的边，都可以在T1中找到一个权值相同且不在T2的边与其对应，而这些边由于是连接不同部分的，所以不可能相同，因此，在T1中也应该有m条权值为bi的边，这和T1中最多m-1条权值为bi的边矛盾。因此，不存在i,使得的aibi，即两个边权序列应该相同。,Arctic Network POJ2349,你现在有一个集合，一开始集合为空，每次你会得到一对个质数，然后如果集合中存在若干个数对，将这些数对和你得到的数对中所有的数乘起来是完全平方数，那么，就将这个数扔掉，否则就将这个数加入集合。最后输出扔掉的