图论常见模型与分析

1、图论常见模型与思想1强连通分量相关概念：有向图的强连通分量(SCC)是指，对于强连通分量里面的任意两个点u,v，都存在从u到v的路和从v到u的路算法：复杂度均为O(V+E)Kosaraju (两次dfs)Tarjan / Gabow (一次dfs)2Tarjan对图进行DFS，每个SCC都是DFS树的一个子树。在搜索时用堆栈维护当前正在处理的结点，栈顶的若干元素即组成一个SCC。类似求割点的过程，定义Lowu = min(dfnu, lowv, (u,v)为树边dfnv, (u,v)为后向边 )若对某点u有 dfnu = lowu，说明以u为根的子树上的点为一个SCC3tarjan(u) DF

2、Nu=Lowu=+Index / 为u设定dfn和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) / 如果节点u还在栈内(后向边)Lowu = min(Lowu, DFNv) if (DFNu = Lowu) / 节点u是SCC的根repeat v = S.pop / 将v退栈，为该SCC中一个顶点print v until (u= v

3、) 45678强连通分量相关关键点：一个强连通分量内部的所有点，在某种意义上是“等价”的。图中的边存在某种意义上的“传递性”。通过缩点操作可以把复杂的一般有向图转化为DAG，使得问题简化9例题分析Popular Cows (USACO Fall 03)POJ 2186N头奶牛，给出若干个欢迎关系A B，表示A欢迎B，欢迎关系是单向的，但是是可以传递的。另外每个奶牛都是欢迎他自己的。求出被所有的奶牛欢迎的奶牛的数目。奶牛数目N10000直接的欢迎关系数目M5000010例题分析如果A欢迎B，就连一条从A到B的有向边容易发现，在同一个强连通分量里的点具有同样的“受欢迎程度”：能够到达它们的点集是相

4、同的，从它们出发能够到达的点集也是相同的。我们求出原图的强连通分量，然后收缩11例题分析容易发现，新图中唯一的出度为0的点即为所求。因为新图不含有环，这样的点一定存在。如果出度为0的点不唯一则无解。时间复杂度 O(E)12例题分析WTommys Trouble(TOJ2233/TOI 1135)WTommy需要向所有人通知某件事情，因为人数众多，他想出了一个省力的方法：他只通知队中的某些人，然后让这些人去通知所有他们认识的人，这些新被通知的人又去通知更多的人直到最后队中的所有人都被通知到。给定最初时WTommy通知每个人所需的花费，现在他想求出一种方案，使得花费最少，并且保证最终所有人都能被通

5、知到。13例题分析Input4 330 20 10 401 22 12 3Output : 601 N 10000, 0 M 200000 14例题分析同一个强连通分量里，只要有一人被通知即可缩点后得到的DAG中，如果一个点被通知，则它的所有后继结点都会被通知。故只需通知入度为0的点在入度为0的每个点所表示的连通分量中，通知花费最少的那个人，即为最优解O(E)15例题分析NOIP 2009 最优贸易(Trade)C 国有 n 个大城市和 m 条道路（单向或双向），每条道路连接这 n 个城市中的某两个城市。水晶球在各地有不同的价格。某商人准备从1走到n（任何城市可以经过多次），在某个城市买入，并

6、在另一城市卖出，收益即为价格之差。他最多只买入和卖出1次，求最大收益。16例题分析如下图，五城市水晶球价格分别为 4，3，5，6，1 。则最高的方案是14545。在第一次到5时买入，第二次到4时卖出，收益为6 1 = 5 17例题分析若图中无环，则可以DP求解：设vi表示i点的物品价格。令dpi表示从i到N的路径中的最高价格。若从i点买入，则收益为dpi-vi。最终结果即为max(dpi-vi)状态转移方程：dpi = max(vi, maxdpj, 当ij有边时)注意：应排除不能到达N的点18例题分析若图中有环在同一SCC里的全部点的“连通性”是等价的：能够到达它们的点集是相同的，从它们出发

7、能够到达的点集也是相同的。若从此SCC买入，则一定买价格最低的点若从此SCC卖出，则一定买价格最高的点19例题分析最终解法：对原图求SCC并缩点，设新点i中最高价格点为Hi，最低价格点为Li。在新的DAG图上有DP：dpi = max(Hi, maxdpj, 当ij有边时)最终结果为maxdpi Li注意：应排除不能到达N的点20例题分析Poly-time Reductions(Hefei 2008)给定一个有向图G，求一个包含最少边的有向图G，使G和G的传递闭包相同。图的传递闭包是指，若存在边AB, BC，则必存在边ACN = 100, M = 1000021例题分析Input 3 31 2

8、2 31 3Output2Input4 61 22 12 33 23 44 3Output422例题分析求强连通分量，缩点在同一强连通分量内部，最少需要几条边？不同分量之间的边，有哪一种是不必要的？23例题分析先求传递闭包对于边(u,v)，若存在一点k，使得uk且kv，则边(u,v)是不必要的易得一个O(n3)的算法证明？24路径覆盖相关经典模型：给定一有向无环图，要求用最少的不相交路径把所有点覆盖上解法：把原图中的每个点i拆为两个，分别属于X集和Y集。对于原图中的有向边(i，j)，在新图中添加边(Xi, Yj)，得到一个二分图。最小路径覆盖数 = 原图顶点数 新图最大匹配数“拆点”思路广泛应

9、用于此类问题25路径覆盖相关简单解释：原图的路径覆盖和新图的匹配间有对应关系：每条覆盖边都是匹配中的一条边，且只有路径的最后一个点没有被匹配上。路径要求不能相交，恰好对应于匹配中两匹配边不能有公共端点。于是求最大匹配后，不能被匹配上的点，即是路径的最后一个点。有多少个不能被匹配的点，就有多少条路径存在。路径数=原点数匹配边数。因此我们使匹配边数最大，即是使路径数最小。26例题分析Hanoi Tower Troubles Again! (OIBH Contest)ZOJ 1239题目大意：给定柱子数N，按编号从小到大放球，要求：如果该球不在最底数，则该球和它下面一个球的编号之和必须为完全平方数。

10、问对于给定的N，最多能放多少球上去。N=5027例题分析28例题分析考虑一下相关的问题：给k个球，问最少需要多少个柱子才能把它们都放上?如果能解出上述问题，则二分k值即可求解原问题。继续类比球?, 柱子?29例题分析如果a+b是完全平方数(ab)，那么我们连一条有向边(a,b)于是，问题变成了求DAG的最小路径覆盖。因为连边时保证ab，所以无环路径柱子路径不相交同一个球不能用两次30例题分析POJ Monthly / POJ 3216题目大意：城市有Q个城区，有些城区之间有路连接，经过这些路所需时间已知。现在有M个维修任务要进行，已知每个任务的地点、deadline和完成每个任务所需时间。维修

11、工可以从任何一个城区开始，完成任务后可以到另一个城区继续。问至少要派出多少个维修工才能及时任务。(Q=20, M=200)31例题分析Sample Input1 20 1 1 10 1 5 10 Sample Output232例题分析Floyd预处理所有点对间最短路径dis设有任务a,b，如果在完成任务a后还来得及走到b处继续，即deadlinea + cost + disab = deadlineb，则连一条有向边(a,b)33例题分析由建图的过程知，这个有向图中一定不会出现环于是问题转化为DAG的最小路径覆盖经典问题，(点数-最大匹配数)即为最终结果。34Dilworth定理NOIP 1

12、999 导弹拦截导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。给定依次飞来的导弹高度，问(1)一套系统最多拦截多少导弹 (2)拦截所有导弹最少需要几套系统35Dilworth定理第一问是简单的最长不上升子序列O(nlogn)第二问解法一：最小路径覆盖 (复杂度过高)解法二：贪心? 36Dilworth定理偏序关系：定义在集合X上的二元关系，对X中任意元素a,b,c满足三条性质：1. 自反性：aa2. 反对称性：若ab且ba，则a=b3. 传递性：若ab且bc，则ac对于X中任意两元素a,b，若有ab或ba，则称a和b是可比的，否则为不可

13、比。37Dilworth定理一个链C是X的一个子集，它的任意两个元素都可比。 一个反链A是X的一个子集，它的任意两个元素都不能进行比较。Dilworth定理： 最大反链的大小 = 最少可划分成的链的数目38Dilworth定理若在拦截导弹a以后还能拦截导弹b，则认为存在关系ab（易得此为偏序关系）问题一：求最大链问题二：求最少划分成多少个链。由Dilworth定理，等价于求最大的反链在此处，最大的反链，即最长上升子序列O(nlogn)39Dilworth定理思考：能用dilworth定理解决的问题一定能用路径覆盖解决吗？反之是否成立？什么情况下只能用匹配来做？40Dilworth定理HDU 3

14、335 Divisibility给定n个数(n1 ?45广义的路径覆盖类比K=1的情况，不同之处在于，每个左边的点可以匹配多个右边的点，于是把每个点i拆成两个点i和i若i能吃掉j，连边(ij)，容量为1从源点到每个左侧点i连边，容量为K从每个右侧点i到汇点连边，容量为1求最大流F，则n-F即为所求46广义的路径覆盖对于属性完全相同的细菌，因为是完全等价，我们可以任意设定一个顺序，例如，以在输入数据中出现的先后顺序为序，只允许排前面的细菌吃掉排后面的细菌。47SPOJ TOURS有N个城市M条单向道路，道路有长度权值。要求设计出若干条环线，使得每个城市都属于（且仅属于）一条环线。每条环线最少包含

15、两个城市，且经过每个城市最多一次。要求所有环线的总长度之和最小。N = 20048SPOJ TOURSInput:5 81 2 42 1 71 3 103 2 103 4 104 5 105 3 105 4 3 Output:40两条环线：1 3 2 15 4 549广义的路径覆盖思考：环覆盖？与路径覆盖有何区别与联系？可否借用类似的思路？50广义的路径覆盖把每个点拆成两个点，按同样方法得到二分图，我们发现一个环覆盖的方案恰好对应一个完美匹配。于是原问题转化为二分图带权匹配。思考：此方法能否用来解决Hamilton回路问题或TSP问题？51例题分析TC SRM 435 Level 3题目大意是

16、，某公司计划重组管理结构，使所有人员形成一个“森林”状结构，即若干树的集合，每个人只属于一棵树，也就是每个人至多有一个上司，要求树的个数尽可能少。这个公司在之前曾有过一些暂时管理关系，比如A曾经暂时管理过B，B可能也暂时管理过A。如果A暂时管理过B，那么A就认为他比B优秀，而且这种优越感是可传递的，即如果A管理过B，B管理过C，则A也认为他比C优秀。如果A认为自己比B优秀，B也认为自己比A优秀，就说两个人有“互斥优越感”。52例题分析现在要求重组后得到的森林状结构满足：1. 任何人的下属应该是他曾经管理过的人。2. 不应有任何人认为他比自己的直接上司优秀。3. 有“互斥优越感”的人不应当有同一

17、个上司。复杂的条件，奇怪的约束，如何下手？_53例题分析Ans = 1 Ans = 1 Ans = 430123012301254例题分析如果A曾经管理B，我们就连有向边(A, B)，那么“互斥优越感”这个东西很容易让人想到强连通分量，一个SCC内部的所有人都是互斥的。我们首先考虑每个SCC只有一个点的情况，这时候图是一个有向无环图(DAG)，类比DAG上的最小路径覆盖问题，这题我们求的是“最小树覆盖”55例题分析在一个“树覆盖”里，除了根，所有的点都有一个入边。我们要使尽可能多的点有一个入边，且不破坏条件3，即同一个连通分量中所有的点的“父亲”是不同的点。56例题分析对每个SCC作匹配，左边

18、是SCC外的点，右边是SCC内的点，求最大匹配，剩下的没被匹配上的右边的点就不得不做为根所有SCC里没匹配上的点的总和即为所求57二分图交错增广路相关交错增广路是求二分图时的一个概念表示从左侧X集开始，交替经过 未匹配边 已匹配边 未匹配边 已匹配边 未匹配边 的过程。若交错路的两端均为未匹配边，说明找到一条可增广路（此时必停在右侧Y集），此时可以通过交换匹配边和未匹配边，使匹配数+158NOI 2009 TransformN = 10000Sample Input: 51 1 2 2 1Sample Output: 1 2 4 0 359NOI 2009 Transform建立二分图，左右各

19、有N个点，若i点经变换后可能到达j，则在左边的i和右边的j之间相边。问题即为求此图的字典序最小的完美匹配60NOI 2009 Transform如何保证字典序最小？方法一：依次穷举由题意知每个左边点最多与两个右边点相连。从0点开始，假设0点与右边两点中较小点相连，检验剩下图是否仍有完美匹配。若无，则说明0应连另一点。对1点,2点继续此过程。复杂度O(n3)61NOI 2009 Transform方法二：调整首先求一个完美匹配。然后从左边编号最小的点开始，依次判断每个顶点的对应。如果当前顶点对应的点是序号较小顶点，可以直接取得，否则尝试修正。修正的方法是强制将当前顶点对应到另一个序号较小顶点，这必然导致X集合中另一个顶点失配，此时从该顶点开始尝试找一条增广路，如果存在则修正成功，否则修正失败，撤回操作。 复杂度O(n2)62NOI 2009 Transform方法三：贪心Step1. 对于左边或右边度为1的点，其匹配方式是唯一确定的。可以将其依次确定并将对应的边删除，这样可能再次出现度为1的点，重复此过程直至不能继续。Step2