网络流
基本概念
流网络
一个有向图(可以有环),不考虑反向边(任意反向边都可以添加一个中间点转化为非反向边),即$G = (V, E)$
可行流
可行流需满足两个条件
1.容量限制
每条边的流量小于容量
$0 \leq f(u, v) \leq c(u, v)$
2.流量守恒
除源点和汇点外,其余结点不存储流量
$\forall x\in v/\{s,t\} \sum_{(v, x) \in E} f(v, x) = \sum_{(x, v) \in E} f(x, v)$
可行流的流量值
定义
从源点流向汇点的流量值,称为可行流的流量值,记作$|f|$
$|f| = \sum_{(s, v) \in E}f(s, v) - \sum_{(v, s) \in E}f(v, s)$
最大流
流量值最大的可行流
残留网络
定义
残留网络为原流网络加上一些反向边,对于原流网络中不同的可行流,其对应的残留网络也不同
$V_f = V, E_f = E和E中的所有反向边$
$c^′(u, v) = \begin{cases}c(u, v) - f(u, v),\,(u, v) \in E \\ f(v, u), \, (v, u) \in E \end{cases} $
性质
因为残留网络也是一个流网络,所以其也有自己的可行流,记作$|f^′|$
对于$f$和$f^′$有 : $|f + f^′| = |f| + |f^′|$且$f + f^′$也是原流网络的一条可行流
证明
1.$f + f^′$满足容量限制
因为$0 \leq f^′(u, v) \leq c^′(u, v) = c(u, v) - f(u, v)$
所以$0 \leq f^′(u, v) + f(u, v) \leq c(u, v)$
因为$0 \leq f^′(u, v) \leq c^′(u, v) = f(v, u) \leq c(v, u)$
所以$0 \leq f(v, u) - f^′(u, v) \leq c(v, u)$
所以$f + f^′$满足容量限制
2.$f + f^′$满足流量守恒
因为$f$满足流量守恒,且$f^′$满足流量守恒
所以$f + f^′$也满足流量守恒
推论
若残留网络有流量大于0的可行流,则原网络值中的此条可行流一定不是最大流
增广路径
定义
在残留网络中,沿着容量大于0的边走,如果能够走到终点,则称为增广路径,增广路径是简单路径,即无环路径
割
定义
将点集$V$分成两个子集$S$,$T$,满足$S \cup T = V, S \cap T = \varnothing, s \in S, t \in T$,称为流网络的割
割的容量
所有从$S$到$T$的边的容量之和,即$c(S, T) = \sum_{u \in S} \sum_{v \in T} c(u, v)$
最小割
最小的割的容量
割的流量
所有从$S$到$T$的流量 $-$ 所有从$T$到$S$ 的流量,
即$f(S, T) = \sum_{u \in S} \sum_{v \in T} f(u, v) - \sum_{u \in T} \sum_{v \in S} f(u, v)$
(不同可行流有不同的$f(S, T)$)
性质
对于流网络的任何一个割和任何一个可行流都有割的流量一定小于割的容量
$\forall[S, T],f(S, T) \leq C(S, T)$
对于任意可行和任意割一定有$f(S, T) = |f|$
证明
对于两个点集$X$, $Y$($X$, $Y$任意, 可以有交集)
有$f(X, Y) = \sum_{u \in X} \sum_{v \in Y} f(u, v) - \sum_{u \in X} \sum_{v \in Y} f(v, u)$
可得到4个性质
1.$f(X, Y) = -f(Y, X)$
2.$f(X, X) = 0$
3.$f(Z, X \cup Y) = f(Z, X) + f(Z, Y)$
4.$f(X \cup Y, Z) = f(X, Z) + f(Y, Z)$
因为$S \cup T = V, S \cap T = \varnothing$
所以$f(S, V) = f(S, S) + f(S, T)$
$f(S, T) = f(S, V) - f(S, S)$
$f(S, T) = f(\{s\}, V) + f(S - \{s\}, V)$
设$S^′ = S - \{s\}$
$f(S^′, V) = \sum_{u \in S^′} \sum_{v \in V} f(u, v) - \sum_{u \in S^′} \sum_{v \in V} f(v, u)$
$= \sum_{u \in S^′}(\sum_{v \in V} f(u, v) - \sum_{v \in V} f(v, u)) = 0$
所以$f(S, T) = f(\{s\}, V) = |f|$
对于任意可行和任意割有$|f| \leq c(S, T)$
推论 : 最大流 $\leq$ 最小割
最大割最小流定理
定义
对于一个流网络$G = (v, E)$ 有三个等价条件 : $\begin{cases} 1.f是最大流 \\ 2.G_f中不存在增广路 \\ 3.\exists[S, T], |f| = c(S, T) \end{cases}$
证明
1证2
通过反证法
若$f$是最大流,且$|f^′| > 0$
则$|f + f^′| = |f| + |f^′| > |f|$,矛盾
所以当$f$是最大流时,$G_f$中不存在增广路成立
2证3
通过残留网络来创建割
$S$ : 在$G_f$中从$s$出发,沿容量大于0的边走,所有能走到的点
$T$ : $V - S$
对于$x \in S, y \in T$,若$f(x, y) < c(x, y)$,则在残留网络中,可以从$s$走到$y$,矛盾.
所以$f(x, y) = c(x, y)$
对于$x \in T, y \in S$,若$f(x, y) > 0$,则在残留网络中,可以从$s$走到$x$ ,矛盾.
所以$f(x, y) = 0$
综上所述
$|f| = f(S, T)$
$ = \sum_{u \in S}, \sum_{v \in T} f(u, v) - \sum_{u \in S}, \sum_{v \in T} f(v, u)$
$= \sum_{u \in S}, \sum_{v \in T} c(u, v) = c(S, T)$
3证1
由割的流量的性质可得 : 最大流 $\leq$ 最小割
因为 最大流 $\leq c(S, T) = |f|$
且 最大流 $\ge |f|$
所以 最大流 $= |f|$
推论
因为最小割 $\leq c(S, T) = |f| \leq$ 最大流
且 最小割 $\ge$ 最大流
所以 最小割 $=$ 最大流
费用流
所有最大可行流中费用的最小或最大的最大可行流
给每条边附上一个费用$w(u, v)$
则费用流的费用 $= \sum f(u, v) \cdot w(u, v)$
由于其定义,当在残留网络中,存在退流时,费用会减去$f(v, u) \cdot w(u, v)$,所以$w(v, u) = -w(u, v)$
算法
求最大流算法的主要思路
维护一个流网络的残留网络
每次找到该残留网络中的增广路,然后更新残留网络,直到更新后的残留网络中没有增广路
EK算法求最大流
算法思路
每次通过bfs找到一条增广路,记录该条增广路,同时返回该条增广路的流量,然后对增广路上所有边及其反向边进行更新
代码
bool bfs()
{
memset(st, false, sizeof st);
queue<int> q;
q.push(s);
st[s] = true, d[s] = INF;
while (q.size())
{
int u = q.front();
q.pop();
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j] && f[i])
{
st[j] = true;
pre[j] = i;
d[j] = min(d[u], f[i]);
if (j == t) return true;
q.push(j);
}
}
}
return false;
}
int EK()
{
int r = 0;
while (bfs())
{
r += d[t];
for (int i = t; i != s; i = e[pre[i] ^ 1])
f[pre[i]] -= d[t], f[pre[i] ^ 1] += d[t];
}
return r;
}
dinic算法
算法思路
相对于EK算法来说,进行了优化,用dfs一次找出多个增广路并更新
1.先通过bfs对图中每个点进行分层,用d[ver]表示点ver的深度,可以避免dfs时出现环路
2.用dfs找出多个增光路,并更新残留网络
三个额外优化
当前弧优化
使ver每次遍历其边时,从第一条还没满流的边cur[ver]进行遍历,跳过了已经满流的边,即cur[ver]为第k条边时,前k - 1条边一定都满流了
flow < limit
即后面边总的最大流量需小于起前面边能流入的最大流量,能使遍历邻边都能遍历到第一条未满流的边后停下
删除无用的点
如果一个点的后继所有边的总流量为0,说明其不能到达$t$点,所以可以删除这个点,即d[ver] = -1
代码
bool bfs()
{
memset(d, -1, sizeof d);
queue<int> q;
d[s] = 0, q.push(s), cur[s] = h[s];
while (q.size())
{
int u = q.front();
q.pop();
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (d[j] == -1 && f[i])
{
d[j] = d[u] + 1;
cur[j] = h[j];
if (j == t) return true;
q.push(j);
}
}
}
return false;
}
int find(int u, int limit)
{
if (u == t) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i])
{
cur[u] = i;
int j = e[i];
if (d[j] == d[u] + 1 && f[i])
{
int t = find(j, min(f[i], limit - flow));
if (!t) d[j] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic()
{
int r = 0, flow;
while (bfs()) while (flow = find(s, INF)) r += flow;
return r;
}
EK算法求最小\最大费用流
算法思路
在前面EK算法求最大流的问题中,可以知道,EK算法的原理是每次同过bfs知道一条增广路,直到当前流是最大流为止
那么在求最小或最大费用流时,我们只需要将bfs改为spfa,每次找一条最短或最长的增广路,直到当前流时最大流为止即可
代码
bool spfa()
{
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = INF;
while (hh != tt)
{
int u = q[hh ++ ];
if (hh == N) hh = 0;
st[u] = false;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (d[j] > d[u] + w[i] && f[i])
{
d[j] = d[u] + w[i];
pre[j] = i;
incf[j] = min(incf[u], f[i]);
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
return incf[T] > 0;
}
void EK(int &flow, int &cost)
{
flow = cost = 0;
while (spfa())
{
int t = incf[T];
flow += t, cost += t * d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
f[pre[i]] -= t, f[pre[i] ^ 1] += t;
}
}
应用
二分图
二分图匹配
二分图多重匹配
上下界网络流
无源汇上下界可行流
在图$G(V, E)$中,对于每条边,给出其容量下界$c_l$和容量上界$c_u$,但无源汇点,求出其可行流
思路
相对于普通的网络流问题,其不同的是没有源汇点,且每条边增加了容量下界
那么可以得到两个性质 : 1.图中所有点都满足流量守恒 2.对于每条边$c_l(u, v) \leq f(u, v) \leq c_u(u, v)$
但是如果要使用一般的最大流算法来求出该图的最大流,就得先把这个图转化为一般的图,即每条边都没有容量下界的图
建立新图$G^′$
由$$c_l(u, v) \leq f(u, v) \leq c_u(u, v)$$可以得到$0 \leq f(u, v) - c_l(u, v) \leq c_u(u, v) - c_l(u, v)$
那么$f^′(u, v) = f(u, v) - c_l(u, v), c^′(u, v) = c_u(u, v) - c_l(u, v)$
然后考虑容量限制和流量守恒
因为$0 \leq f^′(u, v) \leq c^′(u, v)$所以容量限制满足
对于点u,设$C_入 = \sum_{v \in V} c_l(v, u)$,$C_出 = \sum_{v \in V} f(u, v)$
若$C_入 = C_出$
则u点在$G^′$中流量守恒
若$C_入 \neq C_出$
显然u点在G^′中流量不守恒
为了解决这个问题,可以创建一个虚拟源点S和虚拟汇点T
当$C_入 > C_出$时,从S向u连一条容量和流量都为$C_入 - C_出$的边
当$C_入 < C_出时$,从u向T连一条容量和流量都为$C_出 - C_入$的边
这样,$G^′$中除了源点和汇点的所有点,都满足容量限制和流量守恒
所以,从虚拟源点S流出的所有边和流入虚拟汇点T的所有边必须是满流,$G^′$才能满足流量守恒
那么可以猜测,$G$中的任意一个可行流$f$都可以对应到$G^′$中的一个满流最大流$f^′$
证明
对于$G$中任意一个可行流$f$,将其转化为$G^′$中的一个满流最大流$f^′$后,其满足容量限制和流量守恒
对于$G^′$中任意一个满流最大流$f^′$将其转化为$G$中的一个流,
即每条边加上其容量下界,$0 \leq f(u, v) \leq c(u, v)$满足容量限制
对于每个点u来说,$\sum_{(v, u) \in E^′} f^′(v, u) - \sum_{(u, v) \in E^′} f^′(u, v)+ C_入 - C_出 = \sum_{(v, u) \ in E} f(u, v) - \sum_{(u, v) \in E} f(u, v) = 0$满足流量守恒
所以成立
有源汇上下界最大流和最小流
在图$G(V, E)$中,对于每条边,给出其容量下界$c_l$和容量上界$c_u$,有源汇点,求出其最大流或最小流
思路
以求最大流为例
相对于无源汇上下界流网络而言,该图的区别就是多了源汇点。在无源汇图中,由于不存在源汇点,图中的每个点都满足流量守恒。而在有源汇图中,由于存在源汇点,所以源点和汇点一定是不满足流量守恒的,所以如果我们要参考无源汇的思路,首先得把有源汇图转化为无源汇图。可连一条从汇点指向源点的边,容量为$+∞$,这样所有的点就一定满足流量守恒了。这时,我们就可以参考无源汇的思路,将存在上下界的图转化为只存在上界的图。
那么接下来就只剩下一个问题,如何求,由无源汇上下界可行流我们可以得知,新图中的最大流只会对应原图中的一个可行流,如果要求最大流说明我们还得求额外的东西。这里直接给出结论 :
设$f$为原图中的最大流,$f^′$为新图中S到T的满流最大流,$f_{s,t}^′$为新图中s到t的最大流,那么
$f = f^′ + f_{s,t}^′$
证明
由于$f^′$的特殊性,即所有从S出去的边,和指向T的边一定是满流,所以,$f_{s,t}^′$一定不会流到源点和汇点,说明其只会在原图中拥有点和边间流动。那么$f_{s,t}^′$其实就是一个从s到t的可行流,由之前的定义可知一个图的最大流等于其一条可行流加上该可行流的残留网络中的最大流,所以成立。
若求最小流,也同样成立
$f = f^′ + f_{t,s}^′$
多源汇最大流
一个流网络中存在多个源点和汇点
思路
由于存在多个源点和汇点,所以图中不满足流量守恒的点不止两个,这时我们可以对其进行转化,添加虚拟源汇点$S,T$,从虚拟源点$S$向每个源点连一条容量为$+∞$,从每个汇点向虚拟汇点$T$连一条容量为$+∞$的边,这样便可求出多源汇最大流
关键边
若当前边容量增加后,最大流会变大,那么该边成为关键边
思路
对于任意一个最大流,很容易可以想到的是,如果一条边未满流,则该条边一定不是关键边,所以我们只需要考虑已满流的边。
若一条边$E(u, v)$已经满流,且它为关键边,那么它就有以下性质
在残留网络中,容量为0 (dinic算法)
在残留网络中,存在$S → u$和$v → T$的路径 (dfs遍历)
拆点
我们可以通过设置边的容量来限制边的容量,也可以通过拆点来限制点流过的流量
拆点是将点$u$拆成入点$u_s$和出点$u_t$,然后连接两个点,边的容量就是点能流过的最大的流量
同时也可以在特殊的问题中,将点权转化为边权
最大权闭合图
闭合图
对于一个图$G(V, E)$,它的所有点都不指向点集外的点,那么就称$G$为闭合图。
所以最大权闭合图就是,点权和最大的闭合图
思路
创建虚拟源汇点,$s,t$
对于任意点$u$
若$W_u > 0$,从$s$向$u$连一条容量为$W_u$的边
若$W_u < 0$,从$u$向$t$连一条容量为$-W_u$的边
若$E(u, v)$存在,从$u$向$v$连一条容量为$+∞$的边
其最大权闭合子图和最小割一一对应
证明
定义简单割概念,将所有割边只包括与$s$相连或与$t$相连的边的割成为简单割
先来证明闭合图和简单割一一对应
若$V^′$是闭合图的点集,设$S = \{s\} + V^′$,$T = V - S$
由于$V^′$是闭合图,所以不存在一条权值为$+∞$的割边
若$[S, T]$是一个简单割,则割边一定不包括$V^′$中两个点之间的边,说明$V^′$中任意一个点,不管这么走,还是只会在$V^′$中,那么他就是一个闭合图
所以闭合子图和简单割一一对应
设$V_1 = S - \{s\}$,$V_2 = T - \{t\}$
由于$s$不存在到$t$的边,割中不包含$V_1$∪$V2$内部的边
所以只有$s → V_2$,$V_1 → V_2$ 和 $V_1 → T$两种边,则
$C[S, T] = C[V_1, \{t\}] + C[\{s\}, V_2] = \sum_{i \in V_2^+} W_i + \sum_{i \in V_1^-} (-W_i)$
$W(V_1) = \sum_{i \in V_1^+} W_i + \sum_{i \in V_1^-} W_i = \sum_{i \in V_1^+} W_i - \sum_{i \in V_1^-} -(W_i)$
所以
$C[S, T] + W(V_1) = W(V^+)$
$W(V_1) = W(V^+) - C[S, T]$
由于$W(V^+)$为定值,所以若要使$W(V_1)$最大,则需使$C[S, T]$最小
所以最大权闭合图和最小割一一对应
最大权闭合图也就是$V^′ = S - \{s\}$
最大密度子图
对于一个图$G(V, E)$,$G^′(V^′, E′)$是其一个诱导子图,求$\frac{|E^′|}{|V^′|}$的最大值
思路
首先通过01分数规划对原式进行转化
设$\frac{|E^′|}{|V^′|} = x$
通过二分查找$|E^′| - x \cdot |V^′| > 0$是否能找到,即求$|E^′| - x \cdot |V^′|$的最大值是否大于0
求$|E^′| - x \cdot |V^′|$的最大值,即求$x \cdot |V^′| - |E^′|$的最小值
设$d_i$为点$i$的度数
$x \cdot |V^′| - |E^′| = \sum_{i \in V^′} x - (\frac{\sum_{i \in V^′} di}{2} - \frac{C[V^′, \overline{V^′}]}{2}) = \frac{1}{2}(\sum_{i \in V^′} (2g - d_i) + C[V^′, \overline{V^′}])$
这时我们发现,所求的值与割的容量联系了起来,但多了$\sum_{i \in V^′} (2g - d_i)$这一部分,所以还需对图进行改进
建立虚拟源汇点$s, t$,原图中所有点向$t$连一条容量为$2g - d_i$的边,由于$2g - d_i$可能小于0,所以在此基础上,还得加上一个常量$U$
为了消除常量$U$对所求结果的影响,需要从$s$向原图中每个点连接一条容量为$U$的边
点与点之间的容量为1
$S$到$T$的割值包括三个部分 : $\{s\} → \overline{V^′}$,$V^′ → \overline{V^′}$,$V → {t}$
$C[S, T] = \sum_{v \in V^′} U + \sum_{v \in V^′}(U + 2g - d_v) + \sum_{v \in V^′}\sum_{u \in \overline{V^′}} c(v, u)$
$= \sum_{v \in V^′} U + \sum_{v \in V^′}(U + 2g - d_v + \sum_{u \in \overline{V^′}} c(v, u))$
$= \sum_{v \in V^′} U + \sum_{v \in V^′}(U + 2g - \sum_{u \in {V^′}} c(v, u))$
$= U \cdot n + 2g|V^′| - 2|E^′|$
可知,我们需要求的东西就是$\frac{C[S, T] - U \cdot n}{2}$的最小值,也就是求出最小割即可,最小密度子图也就是$V^′ = S - \{s\}$
扩展
若有边权
将$d_i$的含义改为与这个点相连的边的权值之和的一半,点与点之间的边的容量改为边权的大小即可
若有边权和点权
在上面一个该变得基础上,将每个点向$t$连接的边的容量减少$2p_i$,$p_i$为$i$点的点权
二分图的最小权点覆盖集
原图中所有点权为正,选一些点构成一个点集,使得原图中每条边至少有一个点在点集中,则称这个点集为点覆盖集。最小权点集指,总点权最小的点覆盖集
思路
创建虚拟源汇点$s, t$,创建二分图,将每条边的两个点分别放在二分图的两边,从$S$向二分图左边的点连一条容量为点权的边,从二分图右边的点向$t$连一条容量为点权的边,若两点之间有边,则从左边的点向右边的点连一条容量为$+∞$的边,该图的最小割就是二分图的最小权点覆盖集
证明
证明简单割 对应 点覆盖集
若原图中一个边的两个端点在二分图中的边都不在割中,则一定可以从s走到t,矛盾,所以一个简单割一定对应到一个点覆盖集
证明点覆盖集 对应 简单割
由于其只能选择与点权相关的边,所以割一定简单。因为在最小点覆盖集中,原图的任意一个边的两个点,其一定包含一个,所以若在残留网络中能从s走到t,则证明对这条边来说,一个点也没有选,矛盾,所以一个点覆盖集一定是一个割
最小权点覆盖集也就是与选中割边相连的点的集合
扩展
若有负权点,求最小权点覆盖集时,先将负权点选上,然后再图中删除负权点,再按一般方法求最小权点覆盖集
最大权独立集
独立集指一个点集中,任何两个点间都没有边。最大权独立集就是总点权最大的独立集
最大权独立集 $=$ 所有点的总权值 $-$ 最小权点覆盖
证明
证若$V_1$为点覆盖集,则$V_2 = V - V_1$一定独立集
若$V_2$不是独立集,则证明有两个点之间连有边,即一个边的两个点都没有被$V_1$选中,矛盾
证若 $V_2$独立集,则$V_1 = V - V_2$一定是点覆盖集
若$V_1$不是点覆盖集,则一定存在一条边,其两个点都在$V_2$中,即$V_2$中有两个点之间连有边,矛盾
所以$W(V_1) + W(V_2) = W(V)$
$W(V_2) = W(V) - W(V_1)$
由于$W(V)$为常量,若要使$W(V2)$最大,则需要使$W(V_1)$最小
%%%