文章目录
零、前言一、概念回顾(可略过)1.1流网络1.2流1.3最大流1.4残留网络1.5增广路径1.6流网络的割1.7最大流最小割定理1.7.1证明
1.8Ford-Fulkerson方法
二、Dinic算法2.1EK算法的可优化之处2.2Dinic算法的优化策略2.3Dinic算法原理2.3.1找增广路2.3.2更新剩余容量
2.4算法流程2.5代码实现2.6OJ模板练习
零、前言
关于网络流、最大流基本概念见：最大流—EK算法，流网络，残留网络，定理证明，详细代码-CSDN博客
一、概念回顾(可略过)
已经在最大流—EK算法，流网络，残留网络，定理证明，详细代码-CSDN博客中介绍过
1.1流网络
流网络G = (V , E)是一个有向图，其中每条边(u , v)∈E均有一非负容量c(u , v) ≥ 0。如果(u , v) ∉ E，则c(u , v) = 0。
流网络中有两个特别的点：源点s和汇点t。如例中的工厂和仓库。
1.2流
设f(x , y)是定义在节点二元组(x∈V , y∈V)上的实数函数，且满足：
容量限制
:
f
(
x
,
y
)
≤
c
(
x
,
y
)
容量限制:f(x , y) \le c(x , y)
容量限制:f(x,y)≤c(x,y)
反对称性
:
f
(
x
,
y
)
=
−
f
(
y
,
x
)
反对称性:f(x , y) = -f(y , x)
反对称性:f(x,y)=−f(y,x)
流守恒性
:
∀
x
≠
s
,
x
≠
t
,
∑
(
u
,
x
)
∈
E
f
(
u
,
x
)
=
∑
(
x
,
v
)
∈
E
f
(
x
,
v
)
流守恒性:\forall x \ne s,x \ne t,\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)
流守恒性:∀x=s,x=t,(u,x)∈E∑f(u,x)=(x,v)∈E∑f(x,v)
f(x,y)称为流网络的流函数 , 对于(x , y)∈E , f(x , y)称为边的流量 , c(x , y) - f(x , y)称为边的剩余流量.
流 f 值的定义为
∣
f
∣
=
∑
v
∈
V
f
(
s
,
v
)
\left |f \right | = \sum_{v\in V}f(s,v)
∣f∣=v∈V∑f(s,v) 亦即 , 从源点s发出的总流。如例中每天从工厂发出的冰球的箱数。
1.3最大流
对于一个给定的流网络 , 合法的流函数 f 有很多. 使得流的值最大的流函数被称为网络的最大流 , 此时的流的值被称为网络的最大流量.
1.4残留网络
假定有一个流网络G = (V , E)，其源点为s，汇点为t。设f为G中的一个流，一对顶点u, v∈V。在不超过容量c(u，v)的条件下，从u到v之间可以压入的额外网络流量，就是**(u，v) 的残留容量(residual capacity)**，由下式定义:
c
f
(
u
,
v
)
=
c
(
u
,
v
)
−
f
(
u
,
v
)
c_{f}(u,v) = c(u,v) - f(u,v)
cf(u,v)=c(u,v)−f(u,v)
给定一流网络G = (V , E)和流f，由f压得的G的残留网络是Gf = (V , Ef)，其中：
E
f
=
{
(
u
,
v
)
∈
V
×
V
:
c
f
(
u
,
v
)
>
0
}
E_{f} = \{ (u,v)\in V\times V:c_{f}(u,v)>0 \}
Ef={(u,v)∈V×V:cf(u,v)>0} 即，残留网络包含了流网络的所有点，和残留容量大于0的有向边。
注意Ef中的边既可以是E中的有向边也可以是其反向边，若(u , v)∈E，有f(u , v) < c(u , v)，那么根据流网络的性质可知f(v , u) = -f(u,v)，那么对应残留容量就是c(v , u) - (-f(u,v)) = c(v , u) + f(u , v) > 0，则其反向边也在残留网络中。
由残留网络可以得出引理：
f 为G中的一个流，f‘为Gf中的一个流，那么f + f’仍为流网络G的一个流，其流量为| f + f’ | = | f | + | f‘ |
具体证明可以自己尝试或见《算法导论》
1.5增广路径
已知流网络G = (V , E)和流f，增广路径p为残留网络Gf中由源点s到汇点t的一条简单路径。
根据残留网络的定义，增广路径上的每条边的剩余容量都大于0，则该路径上的每条边都可以额外容纳一定的流量，这也和我们后续求最大流密切相关。
不难想出，增广路径可以增加的最大流量为该路径上边的最小残留容量。
1.6流网络的割
流网络G = (V , E)的割(S , T)将V划分为S和T两部分，使得s∈S，t属于T，通过割的流量为S和T之间边上流量的代数和，但是割的容量仅包含从S到T的边的容量的代数和。
如下图，割(S,T)的流量f(S,T) = 12 - 4 + 11 = 19
容量c(S,T) = 12 + 14 = 26
我们称容量最小的割为最小割。
可以证明f(S , T) = | f | ≤ c(S, T)（证明见《算法导论》）
1.7最大流最小割定理
如果 f是具有源点s和汇点t的流网络G = (V , E)中的一个流，那么下列条件是等价的：
f是G的一个最大流残留网络Gf不包含增广路存在G的某个割(S , T)，有| f | = c(S , T)
1.7.1证明
采用循环证明法，(1) => (2) , (2) => (3) , (3) => (1)
(1) => (2):
很容易证明，采用反证法即可
假设Gf含增广路，那么我们可以在Gf中构造一流f’，| f‘ | = min(cf(u,v) , (u , v) ∈ Ef)，那么f + f’仍为流网络的一个流（由1.4中介绍的引理可知），那么|f + f‘| > | f |，那么f就不是最大流，矛盾，则(1) => (2)成立
(2) => (1):
我们只需要在(2)的条件下构造出一个满足(3)的割即可。
选取集合S = {v ∈ V：Gf中从s到v存在一条通路}，T = V - S，划分(S , T)为一个割。
对所有，u∈S，v∈T，f(u , v) = c(u , v)，否则v就属于S。
由此推出| f | = f(S , T) = c(S , T)
(3) => (1):
也很容易证明，由于由于| f | ≤ c(S, T)，而此时| f | = c(S , T)，故不存在比f更大的流，故f为最大流。
1.8Ford-Fulkerson方法
Ford-Fulkerson方法是最大流的经典求解方法，之所以称之为”方法“而非”算法“，是由于它包含具有不同运行时间的几种实现。
Ford-Fulkerson方法依赖于三种重要思想：残留网络(residual network)、增广路(augmenting path)和割(cut)。这些思想是最大流最小割定理的精髓，这里给出Ford-Fulkerson方法的特定实现。
伪代码如下：
Ford-Fulkerson(G , s , t)
初始化流f = 0
while 流网络中存在增广路p
do 沿着p增加f
return f
二、Dinic算法
2.1EK算法的可优化之处
Dinic算法其实就是对于EK算法的优化。
无论是Dinic算法还是EK算法它们都是基于FF方法来求最大流，我们回看EK算法的实现原理：
bfs找到一条增广路更新增广路上边的剩余容量找不到增广路，算法结束，时间复杂度O(n^2 m)
很明显，EK算法有个问题就是每次只找一条增广路然后进行更新，然后再从源点开始找增广路，我们有如下疑问：
我们能否一次更新多条增广路的剩余容量呢？对于网络中的多条增广路，我们如何尽可能快的找到增广路呢？
2.2Dinic算法的优化策略
搜索顺序优化：根据每个点到源点距离，建立分层图，bfs一层一层地去增广，对于不在当前bfs层的下一层的点不进行进一步搜索，避免往回来回走，降低效率当前弧优化：dfs更新多条增广路容量时，对于每个顶点发出的边，其所在增广路已经更新过的边进行剪枝剩余容量优化：很容易理解，能够增加的流量用完了，就剪枝残枝优化：如果该点不在增广路上就剪枝
1是在bfs中的优化，比较直观，2、3、4是在dfs更新容量中的优化，可以结合后续代码理解
2.3Dinic算法原理
2.3.1找增广路
仍然是bfs往下搜索，直到遇到汇点t，只不过我们枚举每个点u时，将其未访问过的邻接点v的深度d[v]设置为d[u] + 1，即一层一层往下找，后面更新也是一层一层往下更新回溯
2.3.2更新剩余容量
EK算法更新剩余容量的策略是记录增广路上节点的前驱节点，从汇点往前一个一个更新
我们Dinic算法更为高效，对一个点发出去的多条增广路上的点都进行更新，对于要更新的点给其一个容量限制limit，即最多能增加的流量，对于每个邻接点v对其深搜，给v的limit为min(limit , w(u,v))，然后获取深搜v得到的v发出的所有增广路能够增加的流量和incf，对边(u,v)的剩余容量进行更新，当然limit也要相应减少
可见dinic是通过深搜加回溯完成了多条增广路的剩余容量更新。
2.4算法流程
dinic算法不断重复以下步骤，直到在残留网络中无法到达t
bfs建立分层图的同时找增广路dfs从源点开始遍历增广路，回溯时更新剩余容量，初始给源点s的可增加流量上限limit为inf（无穷大） 时间复杂度O(nm^2)，实际中远达不到这个上界，可以解决1e4量级的数据
2.5代码实现
#define int long long
#define N 205
#define M 5005
const int MOD = 10000007;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m, s, t, idx;
int d[N], cur[N], head[N]; // 深度，当前边，前向星头
struct edge
{
int v, c, nxt;
} edges[M << 1];
inline void addedge(int u, int v, int c)
{
edges[idx] = {v, c, head[u]};
head[u] = idx++;
}
bool bfs() // 多路增广，分层搜索优化
{
memset(d, 0, sizeof(d));
queue
q.emplace(s), d[s] = 1;
while (q.size())
{
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = edges[i].nxt)
{
int v = edges[i].v;
if (!d[v] && edges[i].c)
{
d[v] = d[u] + 1;
q.emplace(v);
if (v == t)
return true;
}
}
}
return false;
}
int dfs(int u, int limit)
{
if (u == t)
return limit;
int ret = 0;
for (int i = cur[u]; ~i && limit > 0 ; i = edges[i].nxt)//limit > 0 余量优化
{
cur[u] = i;// 当前弧优化
int v = edges[i].v;
if (d[v] == d[u] + 1 && edges[i].c)
{
int incf = dfs(v, min(limit, edges[i].c));
if (!incf)
d[v] = 0; //剪枝优化
edges[i].c -= incf, edges[i ^ 1].c += incf, ret += incf, limit -= incf;
}
}
return ret;
}
int dinic()
{
int ret = 0;
while (bfs())
memcpy(cur, head, sizeof(head)), ret += dfs(s, inf);
return ret;
}
2.6OJ模板练习
P3376 【模板】网络最大流 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
直接跑板子即可，这道题数据量过小，EK算法也能过
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define sc scanf
#define int long long
#define N 205
#define M 5005
const int MOD = 10000007;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m, s, t, idx;
int d[N], cur[N], head[N]; // 深度，当前边，前向星头
struct edge
{
int v, c, nxt;
} edges[M << 1];
inline void addedge(int u, int v, int c)
{
edges[idx] = {v, c, head[u]};
head[u] = idx++;
}
bool bfs() // 多路增广，分层搜索优化
{
memset(d, 0, sizeof(d));
queue
q.emplace(s), d[s] = 1;
while (q.size())
{
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = edges[i].nxt)
{
int v = edges[i].v;
if (!d[v] && edges[i].c)
{
d[v] = d[u] + 1;
q.emplace(v);
if (v == t)
return true;
}
}
}
return false;
}
int dfs(int u, int limit)
{
if (u == t)
return limit;
int ret = 0;
for (int i = cur[u]; ~i && limit > 0 ; i = edges[i].nxt)//limit > 0 余量优化
{
cur[u] = i;// 当前弧优化
int v = edges[i].v;
if (d[v] == d[u] + 1 && edges[i].c)
{
int incf = dfs(v, min(limit, edges[i].c));
if (!incf)
d[v] = 0; //剪枝优化
edges[i].c -= incf, edges[i ^ 1].c += incf, ret += incf, limit -= incf;
}
}
return ret;
}
int dinic()
{
int ret = 0;
while (bfs())
memcpy(cur, head, sizeof(head)), ret += dfs(s, inf);
return ret;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// freopen("in.txt", "r", stdin);
cin >> n >> m >> s >> t;
int a, b, c;
memset(head, -1, sizeof(head));
for (int i = 0; i < m; i++)
cin >> a >> b >> c, addedge(a, b, c), addedge(b, a, 0);
cout << dinic();
}
好文阅读
发表评论