图论算法总结及图论建模

1、图论算法总结,图的基本概念,图的基本概念,二元组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),成为带权图,或加权图(weightedgraph).权通常代表费用、距离等,

2、可以是正数,也可以是负数稠密性：边和V(V-1)/2相比非常少的称为稀疏图(sparsegraph),它的补图为稠密图(densegraph),路径和圈,一条路径(path)是一个结点序列,路上的相邻结点在图上是邻接的如果结点和边都不重复出现,则称为简单路径(simplepath).如果除了起点和终点相同外没有重复顶点和边,称为圈(cycle).不相交路(disjointpath)表示没有除了起点和终点没有公共点的路.更严格地-任意点都不相同的叫严格不相交路(vertex-disjointpath)-同理定义边不相交(edge-disjointpath)路注意:汉语中圈和环经常混用(包括一些固

3、定术语).由于一般不讨论自环(self-loop),所以以后假设二者等价而不会引起混淆,连通性,如果任意两点都有路径,则称图是连通(connected)的,否则称图是非连通的.非连通图有多个连通分量(connectedcomponent,cc),每个连通分量是一个极大连通子图(maximalconnectedsubgraph),完全图和补图,完全图:N个顶点的图，有N(N-1)/2个节点对于(u,v),若邻接则改为非邻接,若非邻接则改为邻接,得到的图为原图的补图完全图=原图补图团：完全子图,生成树,树：N个点，N-1条边的连通图（无环连通图）生成树:包含某图G所有点的树一个图G是树当且仅当以下

4、任意一个条件成立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（边数）的，在稀疏图上的效率远胜邻接表缺点：查找/删除边不是常数时间,邻接表,一、宽

5、度优先遍历(BFS)二、深度优先遍历(DFS),图的遍历算法,给定图G和一个源点s,宽度优先遍历按照从近到远的顺序考虑各条边.算法求出从s到各点的距离宽度优先的过程对结点着色.白色:没有考虑过的点黑色:已经完全考虑过的点灰色:发现过,但没有处理过,是遍历边界依次处理每个灰色结点u,对于邻接边(u,v),把v着成灰色并加入树中,在树中u是v的父亲(parent)或称前驱(predecessor).距离dv=du+1整棵树的根为s,宽度优先遍历(BFS),题目大意：给出N*M个格子，给出K个已经被淹没的格子，其他格子都是干的，求最大的湖的面积（一个格子的面积视为1），如果两个湿的格子四联通（上下左

6、右），则视为这两个格子同属于一个湖输入格式：第一行N，M，K接下来K个格子的坐标,AvoidTheLakes（NOI题库2405）,Input3453222312311,Output4,样例解释#.#.#.,新发现的结点先扩展得到的可能不是一棵树而是森林,即深度优先森林(Depth-firstforest)特别之处:引入时间戳(timestamp)发现时间dv:变灰的时间结束时间fv:变黑的时间1=dvfv=2|V|,深度优先遍历(DFS),初始化:time为0,所有点为白色,dfs森林为空对每个白色点u执行一次DFS-VISIT(u)时间复杂度为O(n+m),深度优先遍历(DFS),括号结构

7、性质对于任意结点对(u,v),考虑区间du,fu和dv,fv,以下三个性质恰有一个成立:完全分离u的区间完全包含在v的区间内,则在dfs树上u是v的后代v的区间完全包含在u的区间内,则在dfs树上v是u的后代,DFS树的性质,定理(嵌套区间定理):在DFS森林中v是u的后代当且仅当dudvfvfu,即区间包含关系.由区间性质立即得到.,DFS树的性质,一条边(u,v)可以按如下规则分类树边(TreeEdges,T):v通过边(u,v)发现后向边(BackEdges,B):u是v的后代前向边(ForwardEdges,F):v是u的后代交叉边(CrossEdges,C):其他边，可以连接同一个D

8、FS树中没有后代关系的两个结点,也可以连接不同DFS树中的结点判断后代关系可以借助定理1,边的分类,当(u,v)第一次被遍历,考虑v的颜色白色,(u,v)为T边灰色,(u,v)为B边(只有它的祖先是灰色)黑色:(u,v)为F边或C边.此时需要进一步判断dudv:C边(v早就被发现了,为另一DFS树中)时间复杂度:O(n+m)定理:无向图只有T边和B边(易证),边分类算法,if(dv=-1)dfs(v);/树边,递归遍历elseif(fv=-1)show(“B”);/后向边elseif(dvdu)show(“F”);/前向边elseshow(“C”);/交叉边d和f数组的初值均为-1,方便了判断

9、,实现细节,实现细节,DAG:有向无环图拓扑顺序：,拓扑排序算法,对图G使用DFS算法,每次把一个结点变黑的同时加到链表首部ANEXAMPLE定理1:有向图是DAG当且仅当没有返祖边如果有返祖边,有环(易证)如果有环c,考虑其中第一个被发现的结点v,环中v的上一个结点为u,则沿环的路径vu是白色路径,u是v的后代,因此(u,v)是返祖边定理2:该算法正确的得到了一个拓扑顺序的逆序,拓扑排序算法,一、有向图:SCC划分的Kosaraju算法(有兴趣的同学自己看吧)二、有向图:SCC划分的Tarjan算法三、无向图:割顶和桥的判定,图的连通性算法,有向图中,u可达v不一定意味着v可达u.相互可达则

10、属于同一个强连通分量(StronglyConnectedComponent,SCC)有向图和它的转置的强连通分量相同所有SCC构成一个DAG,SCC的概念,Tarjan算法是基于对图深度优先搜索的算法每个强连通分量为搜索树中的一棵子树搜索时，把当前搜索树中未处理的节点加入一个堆栈回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。,tarjan算法(参考byvoid博客),定义：DFN(u)为节点u搜索的次序编号(时间戳)Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。,dfn与low函数,算法伪代码,t

11、arjan(u)DFNu=Lowu=+Index/为节点u设定次序编号和Low初值Stack.push(u)/将节点u压入栈中foreach(u,v)inE/枚举每一条边if(visnotvisted)/如果节点v未被访问过tarjan(v)/继续向下找Lowu=min(Lowu,Lowv)elseif(vinS)/如果节点v还在栈内Lowu=min(Lowu,DFNv)if(DFNu=Lowu)/如果节点u是强连通分量的根repeatv=S.pop/将v退栈，为该强连通分量中一个顶点printvuntil(u=v),算法演示,算法演示,算法演示,算法演示,完整代码,voidtarjan(in

12、ti)intj;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;elseif(instackj,if(DFNi=LOWi)Bcnt+;doj=StapStop-;instackj=false;Belongj=Bcnt;while(j!=i);voidsolve()inti;Stop=Bcnt=Dindex=0;memset(DFN,0,sizeof(DFN);for(i=1;i=N;i+)if(!DFNi)tar

13、jan(i);,N头奶牛(N10000)M对关系（a,b），表示a认为b是受欢迎的关系具有传递性，即若(a,b),(b,c)(a,c)询问有多少头奶牛是被其他所有奶牛认为是受欢迎的,PopularCows(POJ2186),求出所有的强连通分量每个强连通分量缩成一点，则形成一个有向无环图DAG。DAG上面如果有唯一的出度为0的点，则该点能被所有的点可达。那么该点所代表的连通分量上的所有的原图中的点，都能被原图中的所有点可达，则该连通分量的点数就是答案。DAG上面如果有不止一个出度为0的点，则这些点互相不可达，原问题无解，答案为0；,PopularCows(POJ2186),proceduret

14、arjan(u:longint);varp:node;v:longint;beginfu:=false;inc(top);stacktop:=u;instacku:=true;p:=headu;inc(time);dfnu:=time;lowu:=time;whilep.keyudobeginv:=p.key;iffvthenbegintarjan(v);lowu:=min(lowu,lowv);endelsebeginifinstackvthenlowu:=min(lowu,dfnv);end;p:=p.next;end;,iflowu=dfnuthenbegininc(s);whilest

15、acktopudobegininstackstacktop:=false;jdstacktop:=s;top:=top-1;end;instackstacktop:=false;jdstacktop:=s;top:=top-1;end;end;,1.,2.,beginread(n);fori:=1tondobeginnew(headi);headi.key:=i;headi.next:=nil;end;read(m);s:=0;fori:=1tomdobeginread(edgexi,edgeyi);new(p);p.key:=edgeyi;p.next:=headedgexi;headedg

16、exi:=p;end;fillchar(f,sizeof(f),true);fillchar(instack,sizeof(instack),false);top:=0;time:=0;fori:=1tondoiffithentarjan(i);fillchar(s1,sizeof(s1),0);,fori:=1tomdobeginifjdedgexijdedgeyitheninc(s1jdedgexi);end;s2:=0;s3:=0;fori:=1tosdoifs1i0theninc(s2)elsebeginforj:=1tondoifjdj=itheninc(s3);end;ifs2+1

17、=sthenwriteln(s3)elsewriteln(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(lowulowv)lowu=lowv;elseif(lowudfnv)lowu=dfnv;,无向图的LOW函数,在一棵DFS树中根root是割顶当且仅当它至少有两个儿子其他点v是割

18、顶当且仅当它有一个儿子u,从u或者u的后代出发没有指向v祖先(不含v)的B边,则删除v以后u和v的父亲不连通,故为割顶割顶判定算法:对于DFS树根,判断度数是否大于1对于其他点u,如果不是根的直接儿子,且lowu=dfnPu,则它的父亲v=Pu是割点,割顶的判定,Network(POJ1144),voiddfs(intu,intdep)dfnu=lowu=dep;for(inti=0;i=dfnu)cutu=true;/由后继节点搜不到比该点更早的点，则该点是割点elselowu=min(lowu,dfnv);,题目大意：给定一个无向图，求有多少点是割点,边(u,v)为桥当且仅当它不在任何一个

19、简单回路中发现T边(u,v)时若发现v和它的后代不存在一条连接u或其祖先的B边,则删除(u,v)后u和v不连通,因此(u,v)为桥桥的判定算法:发现T边(u,v)时若LOWvdu(注意不能取等号),则(u,v)为桥,桥的判定,Byteotia有n个镇。有的镇被双向的道路连接。每一对镇间最多只有一条直接连接的道路。任意两个镇连通。每个镇刚好有一个市民。他们为孤独所困。每个居民都想看看其他所有居民（去他所在的地方），而且刚好做一次。所以刚好发生了n*(n-1)次访问。不幸的是，一些程序员正在罢工，为了使软件的销售量提高。作为抗议活动的一部分，程序员想把Byteotia的一条道路关闭，阻止通过这条道

20、路。他们正在辩论选择哪一条道路会使得后果最严重。（后果最严重即删去这条道路后访问次数最少）,例题,例题,如图，若删去D,E之间的边，则会减少16次访问，若删去G,H之间的，会减少7次访问。若删除其它边，则不会减少访问次数。,应该删除哪些边？很显然，只有删除桥才会减少访问次数，删去其它的边，图依然保持连通。因此，首先应该求出所有的桥。,例题,然后我们分别考虑每个桥的情况，删去这条边，会导致把图分成2个部分，而这两个部分是不连通的。考虑损失掉的访问，其实就是跨越这两个部分的访问，即|S1|*|S2|次访问，|S1|,|S2|是两个部分的大小。由此，大致的算法就形成了，枚举每一条边，然后计算损失的访

21、问，最后输出答案即可。,例题,proceduretarjan(u:longint);varp:node;v:longint;beginfu:=false;inc(time);lowu:=time;dfnu:=time;p:=headu;whilep.keyudobeginv:=p.key;iffvthenbeginfav:=u;tarjan(v);lowu:=min(lowu,lowv);iflowvdfnuthenbegininc(s);x1s:=u;y1s:=v;end;end,elseiffauvthenlowu:=min(lowu,dfnv);p:=p.next;end;end;fun

22、ctiondfs(u:longint):longint;beginfu:=false;p:=headu;whilep.keyudobeginv:=p.key;iffvthenbegintreeu:=treeu+dfs(v);fav:=u;end;p:=p.next;end;inc(treeu);exit(treeu);end;,1.,2.,functioncount(x:longint):longint;beginwhilefax0dox:=fax;count:=treex;end;beginread(n);fori:=1tondobeginnew(headi);headi.key:=i;he

23、adi.next:=nil;end;read(m);fori:=1tomdobeginread(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;fori:=1tondobeginiffithenbegintime:=0;tarjan(i);end;end;fillchar(f,sizeof(f),true);fillchar(tree,sizeof(tree),0);fillchar(fa,sizeof(

24、fa),0);fori:=1tondobeginiffithentemp:=dfs(i);end;max:=0;,3.,4.,fori:=1tosdobeginc1:=treex1i;c2:=treey1i;ifc1c2thenc3:=(count(c1)-treey1i)*treey1ielsec3:=(count(c2)-treex1i)*treex1i;ifc3maxthenbeginmax:=c3;x2:=x1i;y2:=y1i;end;end;writeln(max,x2,y2);end.,5.,给定一张连通图G（V,E）(V=5,000，E=10,000)询问至少要添加多少条边，使

25、得，任意两点间至少有2条路径可达？,RedundantPaths(POJ3177),RedundantPaths(POJ3177),ifdfnu=lowuthenbegininc(s);whilestacktopudobegininstackstacktop:=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,size

26、of(s2),0);fori:=1tomdobeginif(hashxihashyi)and(maphashxi,hashyi)thenbeginmaphashxi,hashyi:=false;maphashyi,hashxi:=false;inc(s2hashxi);inc(s2hashyi);end;end;s1:=0;fori:=1tosdoifs2i=1theninc(s1);writeln(s1+1)div2);end.,3.,4.,图的最短路问题,SSSP的Spfa算法SSSP的Dijkstra算法差分约束系统Floyd-warshall算法,给定带权图和一个起点s,求s到所有点的

27、最短路(边权和最小的路径)最短路有环吗正环:何必呢,删除环则得到更短路负环:无最短路,因为可以沿负环兜圈子,单源最短路问题(SingleSourceShortestPath),最优性原理:若最短路uv经过中间结点w,则uw和wv的路径分别是u到w和w到v的最短路意义:贪心、动态规划,最优性原理,最短路的表示s到所有点的最短路不需要分别表示最短路树:到每个点都沿着树上的唯一路径走实际代码:记录每个点的父亲predu即可输出最短路:从终点沿着predu递推回起点,最短路的表示,松弛（RELAX）操作一条边(u,v)被称为紧的(tense),如果dist(u)+w(u,v)dist(v)可以松弛：d

28、ist(v)=dist(u)+w(u,v),pred(v)=u结论存在紧的边，一定没有正确的求出最短路树不存在紧的边，一定正确的求出最短路树,SPFA算法,SPFA算法伪代码,SPFA算法,优点：如其名，快速。期望的时间复杂度：O(ke)，其中k为所有顶点进队的平均次数，可以证明k一般小于等于4。有兴趣自己GOOGLE解决写起来很方便缺点：在网格图上的效率很低，接近O（n2）,POJ3259-Wormholes,题目大意：虫洞问题，现在有n个点，m条边，代表现在可以走的通路，比如从a到b和从b到a需要花费c时间，现在在地上出现了w个虫洞，虫洞的意义就是你从a到b花费的时间是-c(时间倒流,并且

29、虫洞是单向的)，现在问你从某个点开始走，能否回到从前,POJ3259-Wormholes,提示：SPFA其实是Bellman-ford算法的优化而Bellman-ford可以用来判断一张图中是否存在负环判断方法为：如果一个点被松弛了n次，那么图中就存在负环,POJ3259-Wormholes,题解：按照题目意思建图，判断图中是否存在负环，存在即可回到过去。,把顶点集合V分成两组：（1）S：已求出的顶点的集合（初始时只含有源点V0）（2）V-S=T：尚未确定的顶点集合,Dijkstra算法（仅适用于无负权边的情况）,将T中顶点按递增的次序加入到S中，保证：（1）从源点V0到S中其他各顶点的长度都

30、不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点距离：从V0到此顶点的最短距离T中顶点距离：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度,Dijkstra算法（仅适用于无负权边的情况）,正确性证明算法流程,Dijkstra算法,Dijkstra算法使用了一个优先队列INSERT(line3),每个结点一次EXTRACT-MIN,每个结点一次DECREASE-KEY(line8,在RELAX过程中),一共|E|次直接实现:O(V2)二项堆:O(ElogV)Fibonacci堆:O(E+VlogV),时间复杂度,在有向图G中，每条边的长度均为1，现给定起点和终

31、点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：1路径上的所有点的出边所指向的点都直接或间接与终点连通。2在满足条件1的情况下使路径最短。注意：图G中可能存在重边和自环，题目保证终点没有出边。请你输出符合条件的路径的长度。,NOIP2014Day2T2寻找道路,输入格式：第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t,NOIP2014Day2T2寻找道路,Input6612132625453415Output3,NOIP2

32、014Day2T2寻找道路,如上图所示，满足条件的路径为1-3-4-5。注意点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。,大致思路：因为路径上的所有点的出边所指向的点都直接或间接与终点连通，所以我们不妨把所有的边反向，然后求t到s的最短路径大致证明：先将所有边按照读入顺序标号所有满足条件1的从s到t路径，在边都反向的情况下，对应一条t到s的路径，并且满足一一对应（因为路径上边的标号都相同）Tips：这里的最短路可以BFS求得（因为路径长度都是1）,NOIP2014Day2T2寻找道路,begin/主程序read(n,m1);fori:=1tondobeginnew(h

33、eadi);headi:=nil;new(head1i);head1i:=nil;end;fori:=1tom1doread(xi,yi);read(a,b);sort(1,m1);m:=0;fillchar(f,sizeof(f),true);x1:=0;y1:=0;fillchar(s,sizeof(s),0);fori:=1tom1dobeginifxi=yithenfxi:=falseelsebeginif(xi=x1)and(yi=y1)thencontinue;inc(sxi);inc(m);x1:=xi;y1:=yi;new(p);p.key:=y1;p.next:=headx1

34、;headx1:=p;new(p);p.key:=x1;p.next:=head1y1;head1y1:=p;end;end;,proceduredfs1(u:longint);/子程序varp:node;v:longint;beginfu:=false;p:=head1u;whilepnildobeginv:=p.key;iffvthenbegininc(s1v);fv:=false;dfs1(v);endelseinc(s1v);p:=p.next;end;end;,1.,2.,fillchar(s1,sizeof(s1),0);fillchar(f,sizeof(f),true);dfs

35、1(b);fillchar(al,sizeof(al),true);fori:=1tondobeginifi=bthencontinue;ifsis1ithenali:=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;,whilehead2nildobeginv:=p.key;if(fv)and(alv)thenbeginfv:=false;inc(tail);qtail.key:=v;qtail.di

36、st:=qhead2.dist+1;ifv=bthenbeginwriteln(qtail.dist);find:=true;break;end;end;p:=p.next;end;iffindthenbreak;iffind=falsethenwriteln(-1);end.,3.,4.,线性规划(linearprogramming,LP):给m*n矩阵A、m维向量b和n维向量c,求出x为向量使得Ax=b,且sumcixi最小可行性问题(feasibilityproblem):只需要任意找出一组满足Ax=b的解向量x差分约束系统(systemofdifferenceconstraints):

37、A的每行恰好一个1和一个-1,其他元素都是0.相当于关于n个变量的m个差分约束,每个约束都形如xj-xi=bk,其中1=i,j=n,1=k=m.,差分约束系统,左边的可行性问题等价于右边的差分约束系统,差分约束系统,约束图:结点是变量,一个约束对应一条弧,若有弧(u,v),则得到xu后,有xv=xu+w(u,v),差分约束系统,定理:如果约束图没有负圈,则可取xu为起点v0到u的最短路长;若约束图有负圈,差分约束系统无解.正确性证明无负圈:由松弛条件可证明每个约束得到满足有负圈:把负圈上的约束条件叠加将得到一个矛盾不等式算法步骤构图,得到n+1个结点m+n条边运行最短路算法,差分约束系统,N个

38、区间，ai,bi问一个整数的集合Z至少需要多少个元素，使得，在第i个区间的范围内至少有ci个整数属于集合Z。SampleInputSampleOutput6,IntervalsPOJ1201,beginread(m);max:=0;fori:=1tomdobeginread(xi,yi,zi);ifximaxthenmax:=xi;ifyimaxthenmax:=yi;end;n:=max;fori:=0tondobeginnew(headi);headi:=nil;end;fori:=0ton-1dobeginnew(p);p.dis:=1;p.key:=i+1;p.next:=headi;

39、headi:=p;end;,fori:=ndownto1dobeginnew(p);p.dis:=0;p.key:=i-1;p.next:=headi;headi:=p;end;fori:=1tomdobeginxi:=xi-1;new(p);p.dis:=-zi;p.key:=xi;p.next:=headyi;headyi:=p;end;k:=n;fori:=0tondobegindisti:=huge;end;tail:=1;head1:=0;q1:=k;fillchar(f,sizeof(f),true);distk:=0;fk:=false;,1.,2.,whilehead1nild

40、obeginv:=p.key;ifdistu+p.disdistvthenbegindistv:=distu+p.dis;iffvthenbegininc(tail);qtail:=v;fv:=false;end;end;p:=p.next;end;fu:=true;end;writeln(abs(dist0);end.,3.,目标：给定图G，求出任意两点的最短路径动态规划的思想设di,j,k是在只允许经过结点1k的情况下i到j的最短路长度则它有两种情况（想一想，为什么）：最短路经过点k，dijk=dikk-1+dkjk-1最短路不经过点k，dijk=dijk-1,Floyd-warshall

41、算法,编程复杂度低，三重循环注意：外层循环是K,Floyd-warshall算法,注意“无穷大”的运算时间复杂度:O(n3)空间复杂度:O(n2),Floyd-warshall算法,杭州有N个景区，景区之间有一些双向的路来连接，现在8600想找一条旅游路线，这个路线从A点出发并且最后回到A点，假设经过的路线为V1,V2,.VK,V1,那么必须满足K2,就是说至除了出发点以外至少要经过2个其他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线，并且花费越少越好。,HDU1599：findthemincostroute,Input：第一行是2个整数N和M（N=100,M

42、=1000)，代表景区的个数和道路的条数。接下来的M行里，每行包括3个整数a,b,c。代表a和b之间有一条通路，并且需要花费c元(c=100)。Output：对于每个测试实例，如果能找到这样一条路线的话，输出花费的最小值。如果找不到的话，输出“Itsimpossible.”。,HDU1599：findthemincostroute,floyd求最小环:抛开Dijkstra算法，进而我们想到用Floyd算法。我们知道，Floyd算法在进行时会不断更新矩阵dist(k)。设distk，i，j表示从结点i到结点j且满足所有中间结点，它们均属于集合1，2，k的一条最短路径的权。其中dist0,i,j即

43、为初始状态i到j的直接距离。对于一个给定的赋权有向图，求出其中权值和最小的一个环。我们可以将任意一个环化成如下形式：u-k-v-(x1-x2-xm)-u(u与k、k与v都是直接相连的)，其中v-(x1-x2-xm)-u是指v到u不经过k的一种路径。,HDU1599：findthemincostroute,在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的

44、最短路径，可是我们如何求出v到u不包含k的最短距离呢?,HDU1599：findthemincostroute,现在我们给k加一个限制条件：k为当前环中的序号最大的节点(简称最大点)。因为k是最大点，所以当前环中没有任何一个点k，即所有点都(x1-x2-.xm)-u属于当前环，所以x1，x2，xmk，即x1，x2xmk-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，求出

45、的路径永远不会包含k+1，k+2，,HDU1599：findthemincostroute,万一所求的最小环中包含k+1，k+2，怎么办呢?的确，如果最小环中包含比k大的节点，在当前u,k,v所求出的环显然不是那个最小环。然而我们知道，这个最小环中必定有一个最大点k0，也就是说，虽然当前k没有求出我们所需要的最小环，但是当我们从k做到k0的时候，这个环上的所有点都小于k0了也就是说在k=k0时一定能求出这个最小环。,HDU1599：findthemincostroute,我们用一个实例来说明：假设最小环为1345621。的确，在u=1，v=4，k=3时，k6，dist3，4，1的确求出的不是4

46、5621这个环，但是，当u=4，v=6，k=5或u=5，v=2，k=6时，distk，v，u表示的都是这条最短路径.所以我们在Floyd以后，只要枚举uv，k三个变量即可求出最小环。时间复杂度为O(n3)。我们可以发现，Floyd和最后枚举u，v，k三个变量求最小环的过程都是u,v,k三个变量，所以我们可以将其合并。这样，我们在k变量变化的同时，也就是进行Floyd算法的同时，寻找最大点为k的最小环。,HDU1599：findthemincostroute,最小生成树（MST,MinimalSpanningTree）,PRIM算法并查集KRUSKAL算法,给定图G求连接每个点的连通图（一定是树

47、）权和尽量小,最小生成树,假设选取若干条边，使得当前的图被分成了若干个连通分量无用边：边的两个端点属于同一个连通分量，但这条边不属于任意一个连通分量安全边：从它出去(即恰好有一个端点在此分量内)的最小边不同的分量可以有相同的安全边结论:MST含有所有安全边,不含无用边.,最小生成树思想,结论:MST含有所有安全边,不含无用边.证明假设有一个分量(黄色),它的安全边e不在T内.则u到v有唯一路径,它经过e,它恰好有一个端点在黄色分量中.由于e是安全边,w(e)w(e),用e替换e得到更小的T,矛盾加入无用边将形成环,最小生成树思想,只关心一棵树T,每次加入T的安全边用堆保存到每个顶点(而非边)的

48、安全边Insert/ExtractMin调用V次,DecreaseKey调用E次二叉堆:O(E+V)logV),Fibonacci堆:O(E+VlogV),PRIM算法,PRIM算法,将编号分别为1N的N个对象划分为不相交集合在每个集合中，选择其中某个元素代表所在集合常见两种操作：合并两个集合查找某元素属于哪个集合,并查集DisjointSet,每个集合用一棵“有根树”表示定义数组fa1.nfai=i，则i表示本集合，并是集合对应树的树根seti=j,ji,则j是i的父节点,并查集DisjointSet,查询x所在集合根节点合并集合a,b,并查集DisjointSet,find(x)while

49、(fax!=x)x=fax;returnx;,最坏情况(logN),merge(a,b)if(height(a)=height(b)height(a)=height(a)+1;fab=a;elseif(height(a)height(b)faa=b;elsefab=a;,(1),思想：每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快步骤:第一步，找到根结点第二步，修改查找路径上的所有节点，将它们都指向根结点,路径压缩优化,find(x)while(x!=fax)fax=find(fax);returnfax;,路径压缩优化,Kruskal,1956年提出把边从小到大排序,每

50、次填加一个安全边如何知道边是否安全?并查集,每次约O(1)总O(ElogE+E(V),Kruskal算法,在二维平面上有N个村庄，坐标（xi,yi）给定为其中的S个村庄配备卫星通信设备，使得配备了卫星通信的村庄间互相都能沟通为每个村庄配备一个无线电，能使其能与距离不超过D的村庄沟通求一种卫星通信设备的分配方案，使得D最小，并且满足任意两个村庄之间能沟通，直接或间接,ArcticNetworkPOJ2349,SampleInputSampleOutput212.13,ArcticNetworkPOJ2349,假设d已知，把所有铺设线路的村庄连接起来，构成一个图。需要卫星设备的台数就是图的连通支的

51、个数。d越小，连通支就可能越多。那么，只需找到一个最小的d，使得连通支的个数小于等于卫星设备的数目。,ArcticNetworkPOJ2349,把整个问题看做一个完全图，村庄就是点，图上两点之间的边的权值，就是两个村庄的直线距离。只需在该图上求最小生成树，d的最小值即为第K长边！因为：最小生成树中的最长k-1条长边都去掉后，正好将原树分成了k个连通分支，在每个连通分支上摆一个卫星设备即可,ArcticNetworkPOJ2349,为什么d不可能比第k长边更小？假设最小生成树T上，第k长边连接的点是a,b，那么将边去掉后，树就分成了两个部分T1和T2要使T1和T2能够通讯，必须在T1中找一点p和T2中的点q相连，若边的长度小于，则在T上用替换就能得到更小的生成树，矛盾。因此找不到长度小于的。对