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

图论算法总结 图的基本概念 图的基本概念 二元组G V E 称为图 graph V为结点 node 或顶点 vertex 集 E为图中结点之间的边的集合 点 用数字0 n 1表示点对 u v 称为边 edge 或称弧 arc 对于边 u v E u和v邻接 adjacent e和u v关联 incident 子图 subgraph 边的子集和相关联的点集 图的基本概念 有向图 边都是单向 unidirectional 的 因此边 u v 是有序数对 有时用弧 arc 专指有向边带权图 可以给边加权 weight 成为带权图 或加权图 weightedgraph 权通常代表费用 距离等 可以是正数 也可以是负数稠密性 边和V V 1 2相比非常少的称为稀疏图 sparsegraph 它的补图为稠密图 densegraph 路径和圈 一条路径 path 是一个结点序列 路上的相邻结点在图上是邻接的如果结点和边都不重复出现 则称为简单路径 simplepath 如果除了起点和终点相同外没有重复顶点和边 称为圈 cycle 不相交路 disjointpath 表示没有除了起点和终点没有公共点的路 更严格地 任意点都不相同的叫严格不相交路 vertex disjointpath 同理定义边不相交 edge disjointpath 路注意 汉语中圈和环经常混用 包括一些固定术语 由于一般不讨论自环 self loop 所以以后假设二者等价而不会引起混淆 连通性 如果任意两点都有路径 则称图是连通 connected 的 否则称图是非连通的 非连通图有多个连通分量 connectedcomponent cc 每个连通分量是一个极大连通子图 maximalconnectedsubgraph 完全图和补图 完全图 N个顶点的图 有N N 1 2个节点对于 u v 若邻接则改为非邻接 若非邻接则改为邻接 得到的图为原图的补图完全图 原图 补图团 完全子图 生成树 树 N个点 N 1条边的连通图 无环连通图 生成树 包含某图G所有点的树一个图G是树当且仅当以下任意一个条件成立G有V 1条边 无圈G有V 1条边 连通任意两点只有唯一的简单路径G连通 但任意删除一条边后不连通 图例 图的表示方法 介绍两种图的表示方法 邻接矩阵与邻接表V V的二维数组A A i j 0 若 i j 不相连 A i j 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 距离d v d u 1整棵树的根为s 宽度优先遍历 BFS 题目大意 给出N M个格子 给出K个已经被淹没的格子 其他格子都是干的 求最大的湖的面积 一个格子的面积视为1 如果两个湿的格子四联通 上下左右 则视为这两个格子同属于一个湖输入格式 第一行N M K接下来K个格子的坐标 AvoidTheLakes NOI题库2405 Input3453222312311 Output4 样例解释 新发现的结点先扩展得到的可能不是一棵树而是森林 即深度优先森林 Depth firstforest 特别之处 引入时间戳 timestamp 发现时间d v 变灰的时间结束时间f v 变黑的时间1 d v f v 2 V 深度优先遍历 DFS 初始化 time为0 所有点为白色 dfs森林为空对每个白色点u执行一次DFS VISIT u 时间复杂度为O n m 深度优先遍历 DFS 括号结构性质对于任意结点对 u v 考虑区间 d u f u 和 d v f v 以下三个性质恰有一个成立 完全分离u的区间完全包含在v的区间内 则在dfs树上u是v的后代v的区间完全包含在u的区间内 则在dfs树上v是u的后代 DFS树的性质 定理 嵌套区间定理 在DFS森林中v是u的后代当且仅当d u d v f v f u 即区间包含关系 由区间性质立即得到 DFS树的性质 一条边 u v 可以按如下规则分类树边 TreeEdges T v通过边 u v 发现后向边 BackEdges B u是v的后代前向边 ForwardEdges F v是u的后代交叉边 CrossEdges C 其他边 可以连接同一个DFS树中没有后代关系的两个结点 也可以连接不同DFS树中的结点判断后代关系可以借助定理1 边的分类 当 u v 第一次被遍历 考虑v的颜色白色 u v 为T边灰色 u v 为B边 只有它的祖先是灰色 黑色 u v 为F边或C边 此时需要进一步判断d u d v C边 v早就被发现了 为另一DFS树中 时间复杂度 O n m 定理 无向图只有T边和B边 易证 边分类算法 if d v 1 dfs v 树边 递归遍历elseif f v 1 show B 后向边elseif d v d u show F 前向边elseshow C 交叉边d和f数组的初值均为 1 方便了判断 实现细节 实现细节 DAG 有向无环图拓扑顺序 拓扑排序算法 对图G使用DFS算法 每次把一个结点变黑的同时加到链表首部ANEXAMPLE定理1 有向图是DAG当且仅当没有返祖边如果有返祖边 有环 易证 如果有环c 考虑其中第一个被发现的结点v 环中v的上一个结点为u 则沿环的路径v u是白色路径 u是v的后代 因此 u v 是返祖边定理2 该算法正确的得到了一个拓扑顺序的逆序 拓扑排序算法 一 有向图 SCC划分的Kosaraju算法 有兴趣的同学自己看吧 二 有向图 SCC划分的Tarjan算法三 无向图 割顶和桥的判定 图的连通性算法 有向图中 u可达v不一定意味着v可达u 相互可达则属于同一个强连通分量 StronglyConnectedComponent SCC 有向图和它的转置的强连通分量相同所有SCC构成一个DAG SCC的概念 Tarjan算法是基于对图深度优先搜索的算法每个强连通分量为搜索树中的一棵子树搜索时 把当前搜索树中未处理的节点加入一个堆栈回溯时可以判断栈顶到栈中的节点是否为一个强连通分量 tarjan算法 参考byvoid博客 定义 DFN u 为节点u搜索的次序编号 时间戳 Low u 为u或u的子树能够追溯到的最早的栈中节点的次序号当DFN u Low u 时 以u为根的搜索子树上所有节点是一个强连通分量 dfn与low函数 算法伪代码 tarjan u DFN u Low u Index 为节点u设定次序编号和Low初值Stack push u 将节点u压入栈中foreach u v inE 枚举每一条边if visnotvisted 如果节点v未被访问过tarjan v 继续向下找Low u min Low u Low v elseif vinS 如果节点v还在栈内Low u min Low u DFN v if DFN u Low u 如果节点u是强连通分量的根repeatv S pop 将v退栈 为该强连通分量中一个顶点printvuntil u v 算法演示 算法演示 算法演示 算法演示 完整代码 voidtarjan inti intj DFN i LOW i Dindex instack i true Stap Stop i for edge e V i e e e next j e t if DFN j tarjan j if LOW j LOW i LOW i LOW j elseif instack j if DFN i LOW i Bcnt do j Stap Stop instack j false Belong j Bcnt while j i voidsolve inti Stop Bcnt Dindex 0 memset DFN 0 sizeof DFN for i 1 i N i if DFN i tarjan i N头奶牛 N 10000 M对关系 a b 表示a认为b是受欢迎的关系具有传递性 即若 a b b c a c 询问有多少头奶牛是被其他所有奶牛认为是受欢迎的 PopularCows POJ2186 求出所有的强连通分量每个强连通分量缩成一点 则形成一个有向无环图DAG DAG上面如果有唯一的出度为0的点 则该点能被所有的点可达 那么该点所代表的连通分量上的所有的原图中的点 都能被原图中的所有点可达 则该连通分量的点数就是答案 DAG上面如果有不止一个出度为0的点 则这些点互相不可达 原问题无解 答案为0 PopularCows POJ2186 proceduretarjan u longint varp node v longint beginf u false inc top stack top u instack u true p head u inc time dfn u time low u time whilep keyudobeginv p key iff v thenbegintarjan v low u min low u low v endelsebeginifinstack v thenlow u min low u dfn v end p p next end iflow u dfn u thenbegininc s whilestack top udobegininstack stack top false jd stack top s top top 1 end instack stack top false jd stack top s top top 1 end end 1 2 beginread n fori 1tondobeginnew head i head i key i head i next nil end read m s 0 fori 1tomdobeginread edgex i edgey i new p p key edgey i p next head edgex i head edgex i p end fillchar f sizeof f true fillchar instack sizeof instack false top 0 time 0 fori 1tondoiff i thentarjan i fillchar s1 sizeof s1 0 fori 1tomdobeginifjd edgex i jd edgey i theninc s1 jd edgex i end s2 0 s3 0 fori 1tosdoifs1 i 0theninc s2 elsebeginforj 1tondoifjd j itheninc s3 end ifs2 1 sthenwriteln s3 elsewriteln 0 end 3 4 对于无向连通图G割顶是去掉以后让图不连通的点桥是去掉以后让图不连通的边 割顶与桥 low u 为u及其的后代所能追溯到的最早 最先被发现 祖先点v的dfn v 值类似有向图的计算方式 注意无向图只有T和B边low u dfn u time for u的不等于u的邻居v 不考虑自环if pre v 1 白色点dfs visit v if low u low v low u low v elseif low u dfn v low u dfn v 无向图的LOW函数 在一棵DFS树中根root是割顶当且仅当它至少有两个儿子其他点v是割顶当且仅当它有一个儿子u 从u或者u的后代出发没有指向v祖先 不含v 的B边 则删除v以后u和v的父亲不连通 故为割顶割顶判定算法 对于DFS树根 判断度数是否大于1对于其他点u 如果不是根的直接儿子 且low u dfn P u 则它的父亲v P u 是割点 割顶的判定 Network POJ1144 voiddfs intu intdep dfn u low u dep for inti 0 i dfn u cut u true 由后继节点搜不到比该点更早的点 则该点是割点 elselow u min low u dfn v 题目大意 给定一个无向图 求有多少点是割点 边 u v 为桥当且仅当它不在任何一个简单回路中发现T边 u v 时若发现v和它的后代不存在一条连接u或其祖先的B边 则删除 u v 后u和v不连通 因此 u v 为桥桥的判定算法 发现T边 u v 时若LOW v d u 注意不能取等号 则 u v 为桥 桥的判定 Byteotia有n个镇 有的镇被双向的道路连接 每一对镇间最多只有一条直接连接的道路 任意两个镇连通 每个镇刚好有一个市民 他们为孤独所困 每个居民都想看看其他所有居民 去他所在的地方 而且刚好做一次 所以刚好发生了n n 1 次访问 不幸的是 一些程序员正在罢工 为了使软件的销售量提高 作为抗议活动的一部分 程序员想把Byteotia的一条道路关闭 阻止通过这条道路 他们正在辩论选择哪一条道路会使得后果最严重 后果最严重即删去这条道路后访问次数最少 例题 例题 如图 若删去D E之间的边 则会减少16次访问 若删去G H之间的 会减少7次访问 若删除其它边 则不会减少访问次数 应该删除哪些边 很显然 只有删除桥才会减少访问次数 删去其它的边 图依然保持连通 因此 首先应该求出所有的桥 例题 然后我们分别考虑每个桥的情况 删去这条边 会导致把图分成2个部分 而这两个部分是不连通的 考虑损失掉的访问 其实就是跨越这两个部分的访问 即 S1 S2 次访问 S1 S2 是两个部分的大小 由此 大致的算法就形成了 枚举每一条边 然后计算损失的访问 最后输出答案即可 例题 proceduretarjan u longint varp node v longint beginf u false inc time low u time dfn u time p head u whilep keyudobeginv p key iff v thenbeginfa v u tarjan v low u min low u low v iflow v dfn u thenbegininc s x1 s u y1 s v end end elseiffa u vthenlow u min low u dfn v p p next end end functiondfs u longint longint beginf u false p head u whilep keyudobeginv p key iff v thenbegintree u tree u dfs v fa v u end p p next end inc tree u exit tree u end 1 2 functioncount x longint longint beginwhilefa x 0dox fa x count tree x end beginread n fori 1tondobeginnew head i head i key i head i next nil end read m fori 1tomdobeginread x y new p p next head x p key y head x p new p p next head y p key x head y p end fillchar f sizeof f true s 0 fori 1tondobeginiff i thenbegintime 0 tarjan i end end fillchar f sizeof f true fillchar tree sizeof tree 0 fillchar fa sizeof fa 0 fori 1tondobeginiff i thentemp dfs i end max 0 3 4 fori 1tosdobeginc1 tree x1 i c2 tree y1 i ifc1 c2thenc3 count c1 tree y1 i tree y1 i elsec3 count c2 tree x1 i tree x1 i ifc3 maxthenbeginmax c3 x2 x1 i y2 y1 i end end writeln max x2 y2 end 5 给定一张连通图G V E V 5 000 E 10 000 询问至少要添加多少条边 使得 任意两点间至少有2条路径可达 RedundantPaths POJ3177 RedundantPaths POJ3177 ifdfn u low u thenbegininc s whilestack top udobegininstack stack top false hash stack top s stack top 0 dec top end instack stack top false hash stack top s stack top 0 dec top end end 1 2 fillchar map sizeof map true fillchar s2 sizeof s2 0 fori 1tomdobeginif hash x i hash y i and map hash x i hash y i thenbeginmap hash x i hash y i false map hash y i hash x i false inc s2 hash x i inc s2 hash y i end end s1 0 fori 1tosdoifs2 i 1theninc s1 writeln s1 1 div2 end 3 4 图的最短路问题 SSSP的Spfa算法SSSP的Dijkstra算法差分约束系统Floyd warshall算法 给定带权图和一个起点s 求s到所有点的最短路 边权和最小的路径 最短路有环吗正环 何必呢 删除环则得到更短路负环 无最短路 因为可以沿负环兜圈子 单源最短路问题 SingleSourceShortestPath 最优性原理 若最短路u v经过中间结点w 则u w和w v的路径分别是u到w和w到v的最短路意义 贪心 动态规划 最优性原理 最短路的表示s到所有点的最短路不需要分别表示最短路树 到每个点都沿着树上的唯一路径走实际代码 记录每个点的父亲pred u 即可输出最短路 从终点沿着pred u 递推回起点 最短路的表示 松弛 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 n 2 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 line3 每个结点一次EXTRACT MIN 每个结点一次DECREASE KEY line8 在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寻找道路 Input6612132625453415Output3 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 fori 1tondobeginnew head i head i nil new head1 i head1 i nil end fori 1tom1doread x i y i read a b sort 1 m1 m 0 fillchar f sizeof f true x1 0 y1 0 fillchar s sizeof s 0 fori 1tom1dobeginifx i y i thenf x i falseelsebeginif x i x1 and y i y1 thencontinue inc s x i inc m x1 x i y1 y i new p p key y1 p next head x1 head x1 p new p p key x1 p next head1 y1 head1 y1 p end end proceduredfs1 u longint 子程序varp node v longint beginf u false p head1 u whilepnildobeginv p key iff v thenbegininc s1 v f v false dfs1 v endelseinc s1 v p p next end end 1 2 fillchar s1 sizeof s1 0 fillchar f sizeof f true dfs1 b fillchar al sizeof al true fori 1tondobeginifi bthencontinue ifs i s1 i thenal i false end find false head2 0 tail 1 fillchar q sizeof q 0 q 1 key a q 1 dist 0 fillchar f sizeof f true f a false whilehead2nildobeginv p key if f v and al v thenbeginf v false inc tail q tail key v q tail dist q head2 dist 1 ifv bthenbeginwriteln q tail 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 且sum cixi 最小可行性问题 feasibilityproblem 只需要任意找出一组满足Ax b的解向量x差分约束系统 systemofdifferenceconstraints 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 SampleInputSampleOutput6 IntervalsPOJ1201 beginread m max 0 fori 1tomdobeginread x i y i z i ifx i maxthenmax x i ify i maxthenmax y i end n max fori 0tondobeginnew head i head i nil end fori 0ton 1dobeginnew p p dis 1 p key i 1 p next head i head i p end fori ndownto1dobeginnew p p dis 0 p key i 1 p next head i head i p end fori 1tomdobeginx i x i 1 new p p dis z i p key x i p next head y i head y i p end k n fori 0tondobegindist i huge end tail 1 head1 0 q 1 k fillchar f sizeof f true dist k 0 f k false 1 2 whilehead1nildobeginv p key ifdist u p dis dist v thenbegindist v dist u p dis iff v thenbegininc tail q tail v f v false end end p p next end f u true end writeln abs dist 0 end 3 目标 给定图G 求出任意两点的最短路径动态规划的思想设d i j k 是在只允许经过结点1 k的情况下i到j的最短路长度则它有两种情况 想一想 为什么 最短路经过点k d i j k d i k k 1 d k j k 1 最短路不经过点k d i j k d i j k 1 Floyd warshall算法 编程复杂度低 三重循环注意 外层循环是K Floyd warshall算法 注意 无穷大 的运算时间复杂度 O n 3 空间复杂度 O n 2 Floyd warshall算法 杭州有N个景区 景区之间有一些双向的路来连接 现在8600想找一条旅游路线 这个路线从A点出发并且最后回到A点 假设经过的路线为V1 V2 VK V1 那么必须满足K 2 就是说至除了出发点以外至少要经过2个其他不同的景区 而且不能重复经过同一个景区 现在8600需要你帮他找一条这样的路线 并且花费越少越好 HDU1599 findthemincostroute Input 第一行是2个整数N和M N 100 M 1000 代表景区的个数和道路的条数 接下来的M行里 每行包括3个整数a b c 代表a和b之间有一条通路 并且需要花费c元 c 100 Output 对于每个测试实例 如果能找到这样一条路线的话 输出花费的最小值 如果找不到的话 输出 It simpossible HDU1599 findthemincostroute floyd求最小环 抛开Dijkstra算法 进而我们想到用Floyd算法 我们知道 Floyd算法在进行时会不断更新矩阵dist k 设dist k i j 表示从结点i到结点j且满足所有中间结点 它们均属于集合 1 2 k 的一条最短路径的权 其中dist 0 i j 即为初始状态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的最短距离 dist 0 u k dist 0 k v 我们用Floyd只能求出任意2点间满足中间结点均属于集合 1 2 k 的最短路径 可是我们如何求出v到u不包含k的最短距离呢 HDU1599 findthemincostroute 现在我们给k加一个限制条件 k为当前环中的序号最大的节点 简称最大点 因为k是最大点 所以当前环中没有任何一个点 k 即所有点都 x1 x2 xm u属于当前环 所以x1 x2 xm k 即x1 x2 xm k 1 这样 v到u的最短距离就可以表示成dist k 1 u v dist k 1 v u 表示的是从v到u且满足所有中间结点均属于集合 1 2 k 1 的一条最短路径的权 接下来 我们就可以求出v到u不包含k的最短距离了 这里只是要求不包含k 而上述方法用的是dist k 1 v u 求出的路径永远不会包含k 1 k 2 HDU1599 findthemincostroute 万一所求的最小环中包含k 1 k 2 怎么办呢 的确 如果最小环中包含比k大的节点 在当前u k v所求出的环显然不是那个最小环 然而我们知道 这个最小环中必定有一个最大点k0 也就是说 虽然当前k没有求出我们所需要的最小环 但是当我们从k做到k0的时候 这个环上的所有点都小于k0了 也就是说在k k0时一定能求出这个最小环 HDU1599 findthemincostroute 我们用一个实例来说明 假设最小环为1 3 4 5 6 2 1 的确 在u 1 v 4 k 3时 k 6 dist 3 4 1 的确求出的不是4 5 6 2 1这个环 但是 当u 4 v 6 k 5或u 5 v 2 k 6时 dist k v u 表示的都是这条最短路径 所以我们在Floyd以后 只要枚举u v k三个变量即可求出最小环 时间复杂度为O n3 我们可以发现 Floyd和最后枚举u v k三个变量求最小环的过程都是u v k三个变量 所以我们可以将其合并 这样 我们在k变量变化的同时 也就是进行Floyd算法的同时 寻找最大点为k的最小环 HDU1599 findthemincostroute 最小生成树 MST MinimalSpanningTree 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算法 将编号分别为1 N的N个对象划分为不相交集合在每个集合中 选择其中某个元素代表所在集合常见两种操作 合并两个集合查找某元素属于哪个集合 并查集DisjointSet 每个集合用一棵 有根树 表示定义数组fa 1 n fa i i 则i表示本集合 并是集合对应树的树根set i j ji 则j是i的父节点 并查集DisjointSet 查询x所在集合根节点合并集合a b 并查集DisjointSet find x while fa x x x fa x returnx 最坏情况 logN merge a b if height a height b height a height a 1 fa b a elseif height a height b fa a b elsefa b a 1 思想 每次查找的时候 如果路径较长 则修改信息 以便下次查找的时候速度更快步骤 第一步 找到根结点第二步 修改查找路径上的所有节点 将它们都指向根结点 路径压缩优化 find x while x fa x fa x find fa x returnfa x 路径压缩优化 Kruskal 1956年提出把边从小到大排序 每次填加一个安全边如何知道边是否安全 并查集 每次约O 1 总O ElogE E V Kruskal算法 在二维平面上有N个村庄 坐标 xi yi 给定为其中的S个村庄配备卫星通信设备 使得配备了卫星通信的村庄间互相都能沟通为每个村庄配备一个无线电 能使其能与距离不超过D的村庄沟通求一种卫星通信设备的分配方案 使得D最小 并且满足任意两个村庄之间能沟通 直接或间接 ArcticNetworkPOJ2349 SampleInputSampleOutput212 13 ArcticNetworkPOJ2349 假设d已知 把所有铺设线路的村庄连接起来 构成一个图 需要卫星设备的台数就是图的连通支的个数 d越小 连通支就可能越多 那么 只需找到一个最小的d 使得连通支的个数小于等于卫星设备的数目 ArcticNetworkPOJ2349 把整个问题看做一个完全图 村庄就是点 图上两点之间的边的权值 就是两个村庄的直线距离 只需在该图上求最小生成树 d的最小值即为第K长边 因为 最小生成树中的最长k 1条长边都去掉后 正好将原树分成了k个连通分支 在每个连通分支上摆一个卫星设备即可 ArcticNetworkPOJ2349 为什么d不可能比第k长边更小 假设最小生成树T上 第k长边连接的点是a b 那么将边去掉后 树就分成了两个部分T1和T2要使T1和T2能够通讯 必须在T1中找一点p和T2中的点q相连 若边的长度小于 则在T上用替换就能得到更小的生成树 矛盾 因此找不到长度小于的 对任何比第k长边短的边e 同理也不可能找到替代e的边