图论算法总结及图论建模.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边. 此时需要进一步判断 dudv: 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, 则沿环的路径vu是白色路径, 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 ,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;i=N;i+) if (!DFNi) tarjan(i); ,N头奶牛(N10000) M对关系（a , b），表示a认为b是受欢迎的 关系具有传递性，即若(a,b),(b,c)(a,c) 询问有多少头奶牛是被其他所有奶牛认为是受欢迎的,Popular Cows ( POJ2186 ),求出所有的强连通分量 每个强连通分量缩成一点，则形成一个有向无环图DAG。 DAG上面如果有唯一的出度为0的点，则该点能被所有的点可达。 那么该点所代表的连通分量上的所有的原图中的点，都能被原图中 的所有点可达 ，则该连通分量的点数就是答案。 DAG上面如果有不止一个出度为0的点，则这些点互相不可达，原问题无解，答案为0；,Popular Cows ( POJ2186 ),procedure tarjan(u:longint); var p:node; v:longint; begin fu:=false;inc(top);stacktop:=u; instacku:=true;p:=headu; inc(time);dfnu:=time;lowu:=time; while p.keyu do begin v:=p.key; if fv then begin tarjan(v); lowu:=min(lowu,lowv); end else begin if instackv then lowu:=min(lowu,dfnv); end; p:=p.next; end;,if lowu=dfnu then begin inc(s); while stacktopu do begin instackstacktop:=false; jdstacktop:=s; top:=top-1; end; instackstacktop:=false; jdstacktop:=s; top:=top-1; end; end;,1.,2.,begin read(n); for i:=1 to n do begin new(headi); headi.key:=i; headi.next:=nil; end; read(m); s:=0; for i:=1 to m do begin read(edgexi,edgeyi); new(p); p.key:=edgeyi; p.next:=headedgexi; headedgexi:=p; end; fillchar(f,sizeof(f),true); fillchar(instack,sizeof(instack),false); top:=0;time:=0; for i:=1 to n do if fi then tarjan(i); fillchar(s1,sizeof(s1),0);,for i:=1 to m do begin if jdedgexijdedgeyi then inc(s1jdedgexi); end; s2:=0; s3:=0; for i:=1 to s do if s1i0 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次访问。若删除其它边，则不会减少访问次数。,应该删除哪些边？ 很显然，只有删除桥才会减少访问次数，删去其它的边，图依然保持连通。 因此，首先应该求出所有的桥。,例题,然后我们分别考虑每个桥的情况，删去这条边，会导致把图分成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),最优性原理: 若最短路uv经过中间结点w, 则uw和wv的路径分别是u到w和w到v的最短路 意义: 贪心、动态规划,最优性原理,最短路的表示 s到所有点的最短路不需要分别表示 最短路树: 到每个点都沿着树上的唯一路径走 实际代码: 记录每个点的父亲predu即可 输出最短路: 从终点沿着predu递推回起点,最短路的表示,松弛（RELAX）操作 一条边(u,v)被称为紧的(tense), 如果dist(u)+w(u,v)dist(v) 可以松弛：dist(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(时间倒流,并且虫洞是单向的)，现在问你从某个点开始走，能否回到从前,POJ3259 - Wormholes,提示： SPFA其实是Bellman-ford算法的优化 而Bellman-ford可以用来判断一张图中是否存在负环 判断方法为：如果一个点被松弛了n次，那么图中就存在负环,POJ3259 - Wormholes,题解： 按照题目意思建图，判断图中是否存在负环，存在即可回到过去。,把顶点集合V分成两组： （1）S：已求出的顶点的集合（初始时只含有源点V0） （2）V-S=T：尚未确定的顶点集合,Dijkstra算法（仅适用于无负权边的情况）,将T中顶点按递增的次序加入到S中，保证： （1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点距离：从V0到此顶点的最短距离 T中顶点距离：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度,Dijkstra算法（仅适用于无负权边的情况）,正确性证明 算法流程,Dijkstra算法,Dijkstra算法使用了一个优先队列 INSERT (line 3), 每个结点一次 EXTRACT-MIN, 每个结点一次 DECREASE-KEY (line 8, 在RELAX过程中), 一共|E|次 直接实现: O(V2) 二项堆: O(ElogV) Fibonacci堆: O(E+VlogV),时间复杂度,在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件： 1路径上的所有点的出边所指向的点都直接或间接与终点连通。 2在满足条件1的情况下使路径最短。 注意：图G中可能存在重边和自环，题目保证终点没有出边。 请你输出符合条件的路径的长度。,NOIP2014Day2T2寻找道路,输入格式： 第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。 接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。 最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t,NOIP2014Day2T2寻找道路,Input 6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5 Output 3,NOIP2014Day2T2寻找道路,如上图所示，满足条件的路径为1-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 head2nil 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 = xu + w(u,v),差分约束系统,定理: 如果约束图没有负圈, 则可取xu为起点v0到u的最短路长; 若约束图有负圈, 差分约束系统无解. 正确性证明 无负圈: 由松弛条件可证明每个约束得到满足 有负圈: 把负圈上的约束条件叠加将得到一个矛盾不等式 算法步骤 构图, 得到n+1个结点m+n条边 运行最短路算法,差分约束系统,N个区间，ai,bi 问一个整数的集合Z至少需要多少个元素，使得，在第i个区间的范围内至少有ci个整数属于集合Z。 Sample Input Sample Output 6,Intervals POJ 1201,begin read(m); max:=0; for i:=1 to m do begin read(xi,yi,zi); if ximax 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 head1nil do begin v:=p.key; if distu+p.disdistv then begin distv:=distu+p.dis; if fv then begin inc(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算法,编程复杂度低，三重循环 注意：外层循环是K,Floyd-warshall算法,注意“无穷大”的运算 时间复杂度: O(n3) 空间复杂度: O(n2),Floyd-warshall算法,杭州有N个景区，景区之间有一些双向的路来连接，现在8600想找一条旅游路线，这个路线从A点出发并且最后回到A点，假设经过的路线为V1,V2,VK,V1,那么必须满足K2,就是说至除了出发点以外至少要经过2个其他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线，并且花费越少越好。,HDU1599：find the mincost route,Input：第一行是2个整数N和M（N = 100, M = 1000)，代表景区的个数和道路的条数。 接下来的M行里，每行包括3个整数a,b,c。代表a和b之间有一条通路，并且需要花费c元(c = 100)。 Output：对于每个测试实例，如果能找到这样一条路线的话，输出花费的最小值。如果找不到的话，输出“Its impossible.”。,HDU1599：find the mincost route,floyd求最小环: 抛开Dijkstra算法，进而我们想到用Floyd算法。我们知道，Floyd算法在进行时会不断更新矩阵dist(k)。设distk，i，j表示从结点i到结点j且满足所有中间结点，它们均属于集合1，2， ，k的一条最短路径的权。其中dist0,i,j即为初始状态i到j的直接距离。对于一个给定的赋权有向图， 求出其中权值和最小的一个环。我们可以将任意一个环化成如下形式：u-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，x2xm 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以后，只要枚举uv，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,每个集合用一棵“有根树”表示 定义数组fa1n fai=i，则i表示本集合，并是集合对应树的树根 seti=j, ji, 则 j 是 i 的父节点,并查集 Disjoint Set,查询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; ,路径压缩优化,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能够通