搜索
网络流需要掌握的预备知识最大流算法：SAP或Dinic费用流算法：SPFA流或zkw流或Dijkstra流最大权闭合子图相关建模总览PartI最大流&费用流建模PartII最小割建模PartI最大流&费用流建模基本技巧对点进行限制比如说限制经过次数，限制出入关系，拆点，利用边来完成限制多源多汇（不需要一一对应）建立超级源和超级汇即可存在下界的边设置-inf的边权或新建源点汇点无源汇仅仅是整个网络满足流量平衡有用的模型二分图模型一般用于分配物品，比如将n个物品分配至m个篮子，有一些模型也可以看做物品分配一维模型将一维的点顺次连接，利用差分等技巧进行建模二维模型利用S,T两点建立二分图模型，将二维的点看做边图模型直接在图上建模有用的模型一维模型二分图模型特殊性质平面图最大流平面图最小割对偶图最短路关于费用流的几个有趣的性质在增广过程中，最短路长度不递减如果初始状态不存在负环，则增广过程中不会出现负环引出什么时候需要最大流&费用流建模题目具有什么特征？往往要求我们对一些东西进行分配比如说分配物资，划分路线，或者对抽象的变量进行分配等等基本上是利用自动的“流量分配”来帮助我们解决问题，也会利用流量平衡来建模StageI直接利用最大流定义给一个网络，求最大流不必多说StageII流量分配圆桌问题来自n个不同国家的代表开会，每个国家代表数为ci会场有m张圆桌，每张桌子可容纳mi人不希望有同一个国家的代表在同一张桌子上就餐设计一个合法方案(n,m=300)网络流24题StageII流量分配圆桌问题利用代表和桌子构成的二分图建模用边(u,v)的流量表示国家u的代表中是否有在圆桌v上就餐的利用流量分配求最大流即可StageII流量分配K-完备匹配给出一个有n个点的二分图问是否存在K个不相交的完备匹配（不相交的匹配是指对于同一个节点，每一个匹配中匹配的节点均不相同（是否可以直接k次匈牙利算法(n=100,k=n)经典问题StageII流量分配K-完备匹配Hall定理：若一个二分图是k-正则二分图，则该图存在k个不相交的完备匹配K-正则二分图：每个点的度均为k根据霍尔定理，二分图建模，利用流量分配给每个点的度数分配边根据是否满流判断是否有解如何求方案？去掉不在k-正则二分图中的边，再进行k次匈牙利算法StageII流量分配混合图的欧拉回路给出一个既存在有向边，又存在无向边的图问是否存在欧拉回路（欧拉回路：每条边经过且仅经过一次的回路经典问题StageII流量分配混合图的欧拉回路回顾欧拉回路判断方法：每个点的入度=出度无向边的影响：先给无向边任意定向利用流量分配给更正之前的定向和有下界的边处理类似直观的理解：利用最大流算法，对于入度比出度多的点，将多余的入度进行修正，反之亦然。StageII流量分配[SCOI2012]奇怪的游戏给出一个N*M的棋盘，每个格子上有一个数可以给相邻的两个数同时+1，相邻指有公共边求最少多少次操作可以将棋盘上的数变为同一个数如果不可能，则输出-1(N,M=40,所有数=10^9)假设知道最后需要统一变成D，怎么做？StageII流量分配[SCOI2012]奇怪的游戏提示：每次操作限于相邻的，考虑二分染色StageII流量分配[SCOI2012]奇怪的游戏在知道统一变成D后，对矩阵进行二分染色此时操作的必定是一个白格子，一个黑格子然后利用这个进行二分图建模不知道D？当N*M为偶数时，可以二分答案当N*M为奇数时，考虑黑格子比白格子多一个，而黑白格子中数的和均已知，操作不改变他们的差，可以直接算出DStageII流量分配StrongKings有n个队伍，两两都有比赛知道最后每支队伍获胜的场数求最多有多少队伍，他们战胜了所有获胜场数比自己多的队伍N=50POJ-2699StageII流量分配StrongKings贪心：一定存在一种情况，使得题目所求的队伍是获胜场数最多的那些队伍枚举答案后判断是否有解利用二分图模型即可StageII流量分配matrix给出一个n*m的0/1矩阵A给出一个长度为n的向量V，一个长度为m的向量U要求构造一个整数矩阵B，满足：∑A[i][j]*B[i][j]=V[i]∑A[i][j]*B[i][j]=U[j]清华大学2011年百名信息学优秀高中学子夏令营StageII流量分配matrix之前提到的二维模型根据该模型二分图建模A为0/1矩阵是很好而且关键的性质StageII流量分配数字游戏有一列互不相同的数A1…An可以从前往后选数，使得选出的数递增第一次最多可以取多少数假设第一次可以取出M个数，并且以后的每次也必须恰好取出M个数，问最多能取几次？每个数只能取一次UVAStageII大概是在最大流上的基础拓展体现进行流量分配的思路模型灵活多变，主要特征是需要分配的东西没有本质区别难点主要在建模上，关键是意识到需要你分配东西以及明白分配规则利用上界限制流量大小以及流出S的流量利用是否满流判断是否有解StageIIITypeA[Sdoi2010]星际竞速N个星球M条带权边。每条边只能从编号小的到大的。要求经过所有点仅一次。同时可以瞬移，从任意点瞬移到第i点代价为Ai。求花费比赛的最少时间。N=800,M=15000StageIIITypeA[Sdoi2010]星际竞速分析：首先这显而易见是一道图论相关的题目，在尝试使用最短路等常见模型无法解决后，考虑流的模型。使用网络流——本题既要求能够访问每一个点，又要求代价最小，网络流模型难以满足这两个条件。使用费用流，用流量保证每个点访问一次，用费用保证代价最小。将每一次瞬移后的行动看做一条路径，考虑到每一条路径除了第一个点以外都有一个前驱点，可以使用这个条件来建图。（注意必须保证有向图）StageIIITypeA[Sdoi2010]星际竞速解答：建立虚拟源st与虚拟汇en。将每个点都拆成两个两个点，如u-(u,u’)。从st向所有u连边，容量为1费用为0；从所有u’向en连边，容量为1费用为0；若u,v之间在原图中有边，那么在u与v’之间连边，费用为路径费用Puv，容量为1。从st向所有v’连边，费用为瞬移到v点的代价。在这个图上运行费用流，就能得到最小代价。StageIIITypeA[ZJOI2011]营救皮卡丘N个点，M条边，一共有K个人。每个人可以在边上移动。要想摧毁第i号点，必须先摧毁前i-1个点。人经过点就能瞬间摧毁点，并且可以经过被摧毁的点。在摧毁i-1点以前，i点无法经过。求摧毁所有点，所有人走的总路径长度最小值。N=150.StageIIITypeA[ZJOI2011]营救皮卡丘利用下界确保每个点都经过利用费用计算总花费利用容量限制满足K个人比较有趣的是如何限制“在摧毁i-1点以前，i点无法经过。”其实不仅是限制，没有这个条件大概是没法做的。StageIIITypeA[ZJOI2011]营救皮卡丘建图的时候可以事先计算最短路，将无向图变为有向图即可。StageIIITypeABinaryTreeonPlane平面上有N个点每个点可以向比他纵坐标小的点连边要求连成一颗二叉树使得所有边长度和最小CodeforcesRound#170(Div.1)EStageIIITypeB[ctsc1999]家园人类快要灭亡了，要到月球上去谋生存地球和月球之间有n个太空站，每个太空站可以容纳任意多人有m艘太空飞船，第i艘按照(a_i1,a_i2,a_i3…a_ik)的周期经过第a_i1,a_i2…号太空站，每天由当前所在的太空站出发前往下一个，最多能载ci个人现在地球上有s个人要到月球去，问最快需要多少天将地球，月球分别看做0号，n+1号太空站StageIIITypeB[ctsc1999]家园很直观地想和普通图一样建模，求最大流问题仅仅是太空飞船的航线和时间有关那么没关系，给所有太空站加上一维时间即可即给第一天，第二天。。。的第i号太空站都建立一个节点不需要二分答案，每次保留原来的网络，新添加节点即可StageIIITypeB[HNOI2007]紧急疏散发生了火警，所有人员需要紧急疏散！假设每个房间是一个NM的矩形区域。每个格子如果是'.'，那么表示这是一块空地；如果是'X'，那么表示这是一面墙，如果是'D'，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。3=N=20，3=M=20StageIIITypeB[HNOI2007]紧急疏散同样拆点，和上题一致StageIII网络流上的进一步拓展TypeA在流量分配的前提下，增加了下界和费用，达到一个类似k路径覆盖的效果如果在限制点的流量时，也运用到了拆点技巧路径寻找问题的建模关键在于找到一个拓扑图TypeB在流量分配的前提下，和动态规划类似的，给每个节点加一维状态，即拆点这个的关键大概是正确的找到应该加怎样的状态（上面两题都是答案对应的StageIVTypeA[noi2012]美食节有n种菜品，m位厨师每种菜品有ci份需要烹饪，每位厨师做不同的菜品需要不同的时间每份菜品的等待时间定义为从最开始到制作该份菜品的厨师完成这份菜品要求每一份菜品的等待时间之和最小StageIVTypeA[noi2012]美食节很明显的二分图模型，即给菜品进行分配在StageIII的基础上，费用不再是一次函数，而是和分配到的菜品个数相关但网络流建模却无法实现这点，考虑运用技巧，将费用和每份菜品单独联系起来（这里采用费用提前计算由于本题数据范围很大，所以考虑动态加边StageIVTypeATransportation某国有n座城市，由m条单向道路相连你希望从城市1将k个单位的货物运送到城市n道路很不安全，如果一次携带x个单位的货物，需要花费ai*x^2的费用，每条道路还有容量限制货物必须以整数为单位携带求最小花费Transportation,Harbin2010,LA5095StageIVTypeATransportation和上题类似，在StageIII的基础上改变了费用的函数同样的，我们利用差分，将费用和每个单位的货物联系起来即可StageIVTypeBPainttheRoads某个有n个城市，m条单向道路要求粉刷一些道路，使得被粉刷的道路组成一些没有公共边的回路且每个城市恰好在k条回路上要求被粉刷的道路长度和最小PainttheRoads,Dhaka2006,LA2197StageIVTypeBPainttheRoads在StageIII的基础上，删除源汇的网络流拆点后每个点的度数限制为k对于下界直接使用新建源汇的方法若使用-inf的方法，则可以套用StageV前提到的消负环算法StageIV在StageIII的基础上，费用，源汇等发生了变化但还是没有脱离分配流量的思路TypeA费用可以是函数注意，这一问题是有局限性的，费用必须是凸函数才能保证正确TypeB可以无源汇StageV虽说是StageV，但也只是一些简单运用而已真正困难的还是如何发现模型，永远不要忘记网络流这一强力工具TypeA是一个新模型，其实运用起来很简单，关键是能创造出类似的模型TypeB是一个一维模型建模的普遍做法，不过只是很简单的一种思