图论常见模型与分析

《图论常见模型与分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、为根的子树上的点为一个SCC3tarjan(u){DFN[u]=Low[u]=++Index//为u设定dfn和Low初值Stack.push(u)//将节点u压入栈中foreach(u,v)inE//枚举每一条边if(visnotvisted)//如果节点v未被访问过(树边)tarjan(v)//继续向下找Low[u]=min(Low[u],Low[v])elseif(vinS)//如果节点u还在栈内(后向边)Low[u]=min(Low[u],DFN[v])if(DFN[u]==Low[u])//节点u是SCC的根repeatv=S.pop//将v退栈，为该SCC中一个顶点pri

3、ntvuntil(u==v)}45678强连通分量相关关键点：一个强连通分量内部的所有点，在某种意义上是“等价”的。图中的边存在某种意义上的“传递性”。通过缩点操作可以把复杂的一般有向图转化为DAG，使得问题简化9例题分析PopularCows(USACOFall03)POJ2186N头奶牛，给出若干个欢迎关系AB，表示A欢迎B，欢迎关系是单向的，但是是可以传递的。另外每个奶牛都是欢迎他自己的。求出被所有的奶牛欢迎的奶牛的数目。奶牛数目N≤10000直接的欢迎关系数目M≤5000010例题分析如果A欢迎B，就连一条从A到B的有向边容易发现，在同一个强连通分量里的点具有同样的“受欢迎程

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

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

6、城市买入，并在另一城市卖出，收益即为价格之差。他最多只买入和卖出1次，求最大收益。16例题分析如下图，五城市水晶球价格分别为4，3，5，6，1。则最高的方案是14545。在第一次到5时买入，第二次到4时卖出，收益为6–1=517例题分析若图中无环，则可以DP求解：设v[i]表示i点的物品价格。令dp[i]表示从i到N的路径中的最高价格。若从i点买入，则收益为dp[i]-v[i]。最终结果即为max(dp[i]-v[i])状态转移方程：dp[i]=max(v[i],max{dp[j],当ij有边时})注意：应排除不能到达N的点18例题分析若图中有环……在同一SCC里的全部点的

7、“连通性”是等价的：能够到达它们的点集是相同的，从它们出发能够到达的点集也是相同的。若从此SCC买入，则一定买价格最低的点若从此SCC卖出，则一定买价格最高的点19例题分析最终解法：对原图求SCC并缩点，设新点i中最高价格点为H[i]，最低价格点为L[i]。在新的DAG图上有DP：dp[i]=max(H[i],max{dp[j],当ij有边时})最终结果为max{dp[i]–L[i]}注意：应排除不能到达N的点20例题分析Poly-timeReducti