最大流问题（Maximum-Flow Problem）：
整理摘自刘汝佳《算法入门竞赛（第二版）》
假设把一些物品从节点s（称为“源点”）运送到节点t（称为“汇点”），可以从其他节点中转。
各条有向边的权表示最多能有多少个物品从这条边的起点直接送到这条边终点。
如图，每条边的第一个数字表示实际运送的物品书，而第二个则是题目中的上限。
对于每一条边(u,v)，
它的物品上限称之为“容量capacity”，记为c(u,v)（c(u,v)=0是该边不存在）。
它的实际运送量称之为“流量flow”，记为f(u,v)（f(u,v)=-f(v,u)）。
该问题所求的是把最多的物品从源点s运到汇点t，其他节点都只作为中转。
因此对除了s和t外的任意节点u，\(\sum_{(u,v)\in E}^{}f(u,v)=0\)。
解法：增广路算法(Edmonds-Karp)
概括：从零流开始不断增加流量，保持每次增加流量后都满足容量限制(f(u,v)<=c(u,v))、斜对称型(f(u,v)=-f(v,u))和流量平衡(除了s和t外的任意节点u，\(\sum_{(u,v)\in E}^{}f(u,v)=0\)，也对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。),直到没有增广路为止。
详解：首先，计算出残量（残余容量）网络：r(u,v)=c(u,v)-f(u,v)
再基于任何一条从s到t的又向道路都对应一条原图的增广路（augmenting path），求出该道路所有残量的最小值d，把对应边上的流量加上d即可。
显然，只要残量网络中仍有增广路，流量就能增大。如果没有增广路，则当前流就是最大流。
评论 (0)
