网络流学习笔记
引入+概念
网络
网络是指一个有向图 \(G = (V, E)\)。
每条边 \((u, v) \in E\) 都有一个权值 \(c(u, v)\)，称之为容量，当 \((u, v) \notin E\) 时有 \(c(u, v) = 0\)。
其中有两个特殊的点：源点 \(s\) 和汇点 \(t\)，其中 \(s, t \in V\)，并且 \(s \neq t\)。
流
设 \(f(u, v)\) 定义在二元组 \((u \in V, v \in V)\) 上的实数函数且满足：
1.容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 \(f(u, v) \leq c(u, v)\)；
2.斜对称性：每条边的流量与其相反边的流量之和为 \(0\)，即 \(f(u, v) = -f(v, u)\)；
3.流守恒性：从源点流出的流量等于汇点流入的流量。
那么称 \(f\) 为网络 \(G\) 的流函数。对于 \((u, v) \in E\)，\(f(u, v)\) 称为边的 流量，\(c(u, v) - f(u, v)\) 成为边的剩余容量。整个网络的流量为 \(\sum_{(s, v) \in E} f(s, v)\)，即 从源点发出的所有流量之和
（以上内容摘自 OI-Wiki）
关于网络流问题，常见的有最大流，最小割，费用流等。实际上，对于网络和流的概念我们目前并不需要深入研究，理解即可。在 OI 中对网络流的考察，更偏向于抽象建模能力而非算法本身。
网络最大流
求解网络最大流的基本思路就是寻找增广路。我们将 \(G\) 上一条从 \(s\) 到 \(t\) 的路径称为增广路，而对于一条增广路，我们给每一条边 \((u, v)\) 都加上等量的流量，以使整个网络的流量增加，这一过程称为增广。
这里有两种算法求解网络最大流—— EK(Edmond-Karp) 算法和 Dinic 算法。
Edmond-Karp 算法
算法思想
利用 bfs 不断寻找增广路，直到无法增广为止。
算法过程
-
从 \(s\) 开始 bfs，如果可以到 \(t\) 则我们找到了新的增广路；
-
对于增广路 \(p\)，我们计算出 \(p\) 经过的边的剩余容量的最小值 \(\Delta = \min_{(u, v) \in p}c(u, v)\)。我们给 \(p\) 上每条边都加上 \(\Delta\) 流量，并给它们的反向边都退掉 \(\Delta\) 流量，令最大流增加了 \(\Delta\)；
-
修改原图 \(G\)，在新的图 \(G\) 上重复上述过程，直到无法找到新的增广路。
复杂度
上界 \(O(nm^2)\)，一般跑不满。（本蒟蒻不会证qwq）。
代码
#include<bits/stdc++.h>
using namespace std;
int n, m, s, t;
const int N = 205, M = 5050;
const long long inf = 1111111111111111111;
int head[N], tot = 1, pre[N];
long long incf[N]; bool vis[N];
struct node
{
int nxt, to, w;
}edge[M<<1];
void add(int u, int v, int w)
{
edge[++tot].nxt = head[u];
edge[tot].to = v;
edge[tot].w = w;
head[u] = tot;
edge[++tot].nxt = head[v];
edge[tot].to = u;
edge[tot].w = 0;
head[v] = tot;
}//利用链式前向星连续加边的性质来处理正向边与反向边，注意从 2 开始。
bool bfs()
{
memset(vis, 0, sizeof(vis));//标记已经经过的点。
queue<int> q;
q.push(s); vis[s] = 1;
incf[s] = inf;
while(q.size())
{
int x = q.front(); q.pop();
for(int i = head[x]; i; i = edge[i].nxt)
{
if(edge[i].w!=0)
{
int y = edge[i].to;
if(vis[y]) continue;
incf[y] = min(incf[x], 1ll*edge[i].w);
pre[y] = i;
q.push(y); vis[y] = 1;
if(y == t) return 1;
}
}
}
return 0;
}
long long maxflow = 0;
void update()
{
int x = t;
while(x != s)
{
int i = pre[x];
edge[i].w -= incf[t];
edge[i^1].w+=incf[t];
x = edge[i^1].to;
}
maxflow += incf[t];
}
int main()
{
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i = 1; i<=m; i++)
{
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
add(u, v, c);
}
while(bfs()) update();
printf("%lld", maxflow);
return 0;
}
Dinic 算法
其实我们更常用的是 Dinic 算法，它复杂度要比 EK 算法优秀（理论上界 \(n^2m\)，本蒟蒻还是不会证xwx）。
算法思想
在增广前先对 \(G\) 进行 bfs 分层，即按照点 \(u\) 到 \(s\) 的距离分为若干层，使每次只能使 \(u\) 的流量向下一层流去。
算法过程
- 从 \(s\) 开始 bfs 图 \(G\)，求出每个点的层次；
- dfs 全图，同时对各边的容量进行减少或退回；
- 对新的图 \(G\)，重复上述过程，直到无法 bfs 到 \(t\)；
代码
注：Dinic 算法不进行当前弧优化复杂度是不对的，所以下面代码不保证复杂度正确
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 205, M = 5050;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int s, t;
int tot = 1;
int head[N];
struct node{
int nxt, to;
ll w;
}edge[M<<1];
void add(int u, int v, ll w){
edge[++tot].nxt = head[u];
edge[tot].to = v;
edge[tot].w = w;
head[u] = tot;
}
void Add(int u, int v, int w){
add(u, v, w);
add(v, u, 0);
}
int dep[N];
bool bfs(){
queue<int> q;
memset(dep, 0, sizeof(dep));
dep[s] = 1;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = head[u]; i; i = edge[i].nxt){
int v = edge[i].to;
if((edge[i].w>0)&&(!dep[v])){
dep[v] = dep[u]+1;
q.push(v);
}
}
}
if(dep[t]){
return 1;
}
return 0;
}
ll dfs(int u, ll flow){
if(u == t) return flow;
for(int i = head[u]; i; i = edge[i].nxt){
int v = edge[i].to;
if(dep[v] == dep[u]+1&&(edge[i].w)){
ll fl = dfs(v, min(flow, edge[i].w));
if(fl>0){
edge[i].w -=fl;
edge[i^1].w+=fl;
return fl;
}
}
}
return 0;
}
ll ans;
int n, m;
int main(){
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i = 1; i<=m; ++i){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
Add(u, v, w);
}
while(bfs()){
ll d = dfs(s, INF);
while(d){
ans+=d;
d = dfs(s, INF);
}
}
printf("%lld\n", ans);
return 0;
}
当前弧优化
刚才的过程中，由于我们每次都需要遍历 \(u\) 的每一条出边，导致局部复杂度可能达到 \(O( \left| E \right| ^2)\)。我们可以记录一下之前 \(u\) 循环到哪条边，以此来加速。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 205, M = 5050;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int s, t;
int tot = 1;
int head[N];
struct node{
int nxt, to;
ll w;
}edge[M<<1];
void add(int u, int v, ll w){
edge[++tot].nxt = head[u];
edge[tot].to = v;
edge[tot].w = w;
head[u] = tot;
}
void Add(int u, int v, int w){
add(u, v, w);
add(v, u, 0);
}
int dep[N], cur[N];//cur用来记录当前到了哪条边，防止重复遍历
bool bfs(){
queue<int> q;
memset(dep, 0, sizeof(dep));
dep[s] = 1;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = head[u]; i; i = edge[i].nxt){
int v = edge[i].to;
if((edge[i].w>0)&&(!dep[v])){
dep[v] = dep[u]+1;
q.push(v);
}
}
}
if(dep[t]){
return 1;
}
return 0;
}
ll dfs(int u, ll flow){
if(u == t) return flow;
for(int &i = cur[u]; i; i = edge[i].nxt){//利用取址符每次修改当前弧
int v = edge[i].to;
if(dep[v] == dep[u]+1&&(edge[i].w)){
ll fl = dfs(v, min(flow, edge[i].w));
if(fl>0){
edge[i].w -=fl;
edge[i^1].w+=fl;
return fl;
}
}
}
return 0;
}
ll ans;
int n, m;
int main(){
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i = 1; i<=m; ++i){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
Add(u, v, w);
}
while(bfs()){
for(int i = 1; i<=n; ++i){
cur[i] = head[i];//记得每次bfs后初始化
}
ll d = dfs(s, INF);
while(d){
ans+=d;
d = dfs(s, INF);
}
}
printf("%lld\n", ans);
return 0;
}