最大流

给定一个有向图G=(V,E),其中每一条边(u,v)均有一个非负数的容量值,记为c(u,v)≥0。同时在图中有两个特殊的顶点,源点S和汇点T
从源点S到汇点T的最大可行流量,这个问题也被称为最大流问题

对于任意一个时刻,设f(u,v)实际流量,则整个图G的流网络满足3个性质:

  1. 容量限制:对任意u,v∈ V,f(u,v)≤c(u,v)。

  2. 反对称性:对任意u,v∈ V,f(u,v) = -f(v,u)。从u到v的流量一定是从v到u的流量的相反值。

  3. 流守恒性:对任意u,若u不为S或T,一定有∑f(u,v)=0,(u,v)∈ E。即u到相邻节点的流量之和为0,因为流入u的流量和u点流出的流量相等,u点本身不会”制造”和”消耗”流量。

最大流最小割

  • 对于一个网络流图G=(V,E),其割的定义为一种点的划分方式:
    将所有的点划分为S和T=V-S两个部分,其中源点s∈ S,汇点t∈ T
  • 对于一个割(S,T),我们定义净流f(S,T)表示穿过割(S,T)的流量之和,即:
    f(S,T) = Σf(u,v) | u∈ S,v∈ T
  • 同时我们定义割的容量C(S,T)为所有从S到T的边容量之和,即:
    C(S,T) = Σc(u,v) | u∈ S,v∈ T
  • 对于任意一个割的净流f(S,T)一定是小于等于割的容量C(S,T)。那也即是,对于网络的任意一个流f一定是小于等于任意一个割的容量C(S,T)。
  • 在所有可能的割中,存在一个容量最小的割,我们称其为最小割
  • 对于任一个网络流图来说,其最大流一定是等于最小割的

最大流最小割定理:
对于一个网络流图G=(V,E),其中有源点s和汇点t,那么下面三个条件是等价的:

  1. 流f是图G的最大流
  2. 残留网络Gf不存在增广路
  3. 对于G的某一个割(S,T),此时f = C(S,T)

最大流多次增广之后,所有的vis点即为S

最小费用最大流

给定网络N=(V,E,c,w,s,t),每一弧(vi,vj)属于E上,除了已给容量cij外,还给了一个单位流量的费用w(vi,vj)≥O(简记为wij)。
所谓最小费用最大流问题就是要求一个最大流f,使得流的总输送费用 W(f)=∑wijfij 最小

建模

多源多汇

加一个超级源 s' 和一个超级汇 t`
s'向每个源引一条有向弧,容量为无穷大
每个汇向t`引一条有向弧,容量为无穷大

结点容量

每个结点有一个允许通过的最大容量,称为结点容量

将每个结点$u$拆为$u_1$和$u_2$两个结点,$u_1$和$u_2$连一条有向弧
可以编号 $u_1 = u,u_2 = u + n$

费用与流量平方成正比

即弧流量为$x$时,费用为$ax^2$
拆边,比如容量为5,费用为a的边
被拆为容量为1,费用为1a 3a 5a 7a 9a的5条边

流量不固定的s-t最小费用流

网络流中费用有正有负
若费用都为正,最小费用流显然为零流

在进行增广时,增广路的权值逐渐增大,最后变为正数,此时应停止增广

二分图多重匹配

在二分图最大匹配中,每个点(不管是X方点还是Y方点)最多只能和一条匹配边相关联
二分图多重匹配允许二分图有多条匹配边

二分图多重最大匹配

最大流

poj1698

二分图多重最佳匹配

费用流

poj2112

最小路径覆盖

观察到每条路径只有第一个结点和最后一个结点入度不等于出度
因此将每个点拆成两个,分为U,V两部分,连边,流量均为1
若没有流量流经V部分的点,则说明其为一条路径的终点
因此n - 最大流即为答案

区间k覆盖问题

数轴上有一些带权值的左闭右开区间,选出权和尽量大的一些区间,
要求任意一个数最多被k个区间覆盖

将每个数作为一个结点,然后与权值为w的区间[u,v)加边,容量为1,费用为-w
S与数轴上所有点加边,容量为k,费用为0
所有区间与T加边,容量为INF,费用为0
跑一个费用流

数值范围大的话先离散化。

最大权闭合子图

给定带权图G,求一个权值和最大的点集,若选择u,存在弧(uv),v也必须在点集中

从S向所有正权点引一条边,容量为权值
所有负权点向T引一条边,容量为权值的相反数

求出最小割后,G-{s}就是最大权闭合子图

  • 子图权值和 = 原图中权值为正的点和 - 最大流

最大密度子图

给一个无向图,找出一个点集,使得这些点之间的边数除以点数(称为子图的密度)的值最大

二分密度mid
对于mid值建图:设置超级源点T,超级汇点T

1,S向所有点建边,容量为M;

2,所有点向T建边,容量为M + 2*mid - d,其中d为该点在无向图中的度数;

3,对于无向边<u, v>,建边u->v 和 v->u,容量为1。

实现:

1,二分枚举比值mid,根据mid值建图,若(M * N – Maxflow())/ 2大于或等于0, l = mid否则r = mid;

2,最后得出的l就是最大密度,根据l值重新建图,求一次最大流Maxflow();

3,在残量网络里面,找到从源点出发能够到达的所有点,这些点就是我们要找的子图里面的点。

注意
无向图G中,任意两个具有不同密度的子图G1、G2,密度差不小于1/N/N。
这个定理很重要,它决定了我们二分查找的精度。 while(r - l >= 1/ N / N)
因此二分后需要将图跑出来然后计算密度(从S开始,走流量小于容量的边,经过的点即这个图)