12/3日记 网络流之最大流
CatWing
·
·
算法·理论
网络流是一种“流问题”，就是与电流、水流等各种“流”为原型的题。最大流只是其中的一部分，求的是从起点出发，能输送到终点的水流最大是多少。最大流问题有三种算法，分别是Ford-Fulkerson、Edmond-Karp和Dinic。下面以P3376这个模版题为例子，逐个讲解。
1.Ford-Fulkerson算法
这个算法的思路是：在残存网络中不断寻找增广路径，每找到一条增广路径，就递增最大流f，并更新残存网络，直到残存网络中不存在增广路径，则此时f即为最终的最大流。
增广路径
概念：一条能从起点s到达终点t的流量大于0的路径
性质：通过增广路径，流量一定会增加
残存网络
概念：用边的剩余容量来表示每条边的网络图
性质：一定是经过寻找增广路径后，将一些边的容量减少了的网络图，才是残存网络
算法具体步骤：
- 寻找增广路径
- 如果找到了，更新最大值，并把正向边都减去这条路径上最小的容量；没找到就退出循环
- 添加增广路径的反向边，容量都是路径上最小的容量
- 形成了新的残存网络
- 回到步骤1
Q&A：
$A$：因为如果每次都找到增广路径就减，直到没有，无法保证计算出的最大流是最优的。加上反向边就相当于加上了一个“反悔机制”，走反向边就意味着撤回上次流经正向边的若干流量，可以保证结果最大化。
**这个算法是采用$dfs$的思想实现**，下面分析一下代码所用到的函数：
（1）$add
**这个函数就是链式前向星存图法，分别记录这条边的第二节点、容量、第一节点上一次的编号，以及把它统计进第一节点的出边编号里。**
```
void add(int u,int v,long long w)
{
to[cnt] = v;
a[cnt] = w;
nt[cnt] = h[u];
h[u] = cnt++;
}
```
（2）$dfs
**这个$dfs$函数其实就是一个递归函数，在不断寻找增广路径，找到了就标记、更新；没找到或到了终点就返回。读入两个参数源点和流入的水流量，返回这次递归的水流量。**
```
long long dfs(int u,long long w)
{
if(u == t)//如果到了终点t，直接返回w，退出
{
return w;
}
b[u] = 1;//有水流流过了
for(int i = h[u];i != -1;i = nt[i])//链式前向星遍历法
{
if(a[i] > 0 && b[to[i]] == 0)//如果还有剩余流量，且这个点之前没有水流
{
long long c = dfs(to[i],min(w,a[i]));//递归dfs
if(c == -1)//不能找到增广路径
{
break;
}
a[i] -= c;//正向边减少c
a[i ^ 1] += c;//反向边增加c（^的意思是奇数+1，偶数-1，正好满足求反向边编号的条件）
return c;
}
}
return -1;//在残存网络中找不到增广路径了
}
```
好了，函数都说完了，上最终代码：（main函数在干什么看注释）
```
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,cnt,to[10005],b[205],h[205],nt[10005];
long long a[10005];
void add(int u,int v,long long w)
{
to[cnt] = v;
a[cnt] = w;
nt[cnt] = h[u];
h[u] = cnt++;
}
long long dfs(int u,long long w)
{
if(u == t)
{
return w;
}
b[u] = 1;
for(int i = h[u];i != -1;i = nt[i])
{
if(a[i] > 0 && b[to[i]] == 0)
{
long long c = dfs(to[i],min(w,a[i]));
if(c == -1)
{
continue;
}
a[i] -= c;
a[i ^ 1] += c;
return c;
}
}
return -1;
}
int main()
{
memset(h,-1,sizeof(h));//初始化，防止循环时无法分辨编号0与没有赋值的区别
memset(nt,-1,sizeof(nt));
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i = 1;i <= m;i++)
{
int u,v;
long long w;
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);//存正向边
add(v,u,0);//存反向边
}
long long ans = 0,c = dfs(s,1e18);//先递归出第一个结果
while(c != -1)//有增广路径
{
memset(b,0,sizeof(b));//清空，方便下次递归
ans += c;//加上这次的流量
c = dfs(s,1e18);//继续dfs递归
}
printf("%lld",ans);
return 0;
}
```
因为FF算法的时间复杂度是$O(m*ans)$，$m$是边数，$ans$是最大流（结果），所以效率极低，此题只能得84分。下面的算法EK，就能AC。
------------
### 2.Edmond-Karp算法
此算法和FF算法几乎一样，只是把$dfs$改成了$bfs$实现。算法大致思路是：将残存网络看作一个无权图然后求$s$到$t$的最短路，这条最短路上的最小剩余流量如果大于$0$，那么就作为增广路径，进行残存网络的更新。
FF算法的时间复杂度受最大流大小影响，而EK算法只受节点数量和边的数量的影响，所以时间复杂度更低。
$add$函数不变，下面分析一下$bfs$函数：
$l$数组是记录走向，就可以实现“反悔机制”；$f$是记录最小值；$q$这个优先队列相当于一个存储器，模拟$bfs$；其他的都和上面一样。
**此函数就是不停地遍历、递归、更新，到了终点就返回$1$，没到就返回$0$。**
```
int bfs()
{
memset(l,-1,sizeof(l));//初始化
queue<int> q;
q.push(s);//先将起点加入队列
f[s] = 1e18;//取最大值，方便min
while(!q.empty())
{
int u = q.front();
q.pop();
if(u == t)//到了终点就退出
{
break;
}
for(int i = h[u];i != -1;i = nt[i])//还是链式前向星
{
if(a[i] > 0 && l[to[i]] == -1)//如果还有水流且要去的点没有其他水流流过
{
l[to[i]] = i;//到to[i]需要走i这条边
f[to[i]] = min(f[u],a[i]);//递归bfs
q.push(to[i]);//入队
}
}
}
return l[t] != -1;//如果能送到终点，返回1，否则0
}
```
好了，直接上代码：
```
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,h[205],nt[10005],to[10005],cnt,l[205];
long long a[10005],f[205];
void add(int u,int v,long long w)
{
to[cnt] = v;
a[cnt] = w;
nt[cnt] = h[u];
h[u] = cnt++;
}
int bfs()
{
memset(l,-1,sizeof(l));
queue<int> q;
q.push(s);
f[s] = 1e18;
while(!q.empty())
{
int u = q.front();
q.pop();
if(u == t)
{
break;
}
for(int i = h[u];i != -1;i = nt[i])
{
if(a[i] > 0 && l[to[i]] == -1)
{
l[to[i]] = i;
f[to[i]] = min(f[u],a[i]);
q.push(to[i]);
}
}
}
return l[t] != -1;
}
int main()
{
memset(h,-1,sizeof(h));
memset(nt,-1,sizeof(nt));
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i = 1;i <= m;i++)
{
int u,v;
long long w;
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);//正向边
add(v,u,0);//反向边
}
long long sum = 0;
while(bfs() == 1)//把源点还能送出去的水全部都送出去，直到送不到终点
{
sum += f[t];//累加
for(int i = t;i != s;i = to[l[i] ^ 1])//还有多余的水，送出去
{
a[l[i]] -= f[t];//正向边减少
a[l[i] ^ 1] += f[t];//反向变边增加
}
}
printf("%lld",sum);
return 0;
}
```
EK算法的时间复杂度是$O(nm^2)$，可以过，愉快AC！
------------
### 3.Dinic算法
前面两个算法分别用了$dfs$和$bfs$，这个算法就是把两个函数结合起来，先用$bfs$分层，再用$dfs$寻找。分层是预处理出源点到每个点的距离（注意每次循环都要预处理一次，因为有些边可能容量变为$0$不能再走）。我们只往层数高的方向增广，可以保证不走回头路也不绕圈子。
**优化：**
1. **多路增广**：节省很多花在重复路线上的时间，在某点$dfs$找到一条增广路后，如果还剩下多余的流量未用，继续在该点$dfs$尝试找到更多增广路。
2. **当前弧优化**：因为在Dinic算法中，一条边增广一次后就不会再次增广了，所以下次增广时不需要再考虑这条边。我们把$h$数组复制一份，但不断更新增广的起点。
这个算法，码量较大，有三个函数，但是和前面的函数几乎一样，所以直接上最终代码。（带注释）
```
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,h[205],nt[10005],to[10005],l[205],c[205],cnt;
//l数组为各点到起点的深度，c数组为当前弧优化的增广起点
long long a[10005];
void add(int u,int t,long long d)//链式前向星存图
{
to[cnt] = t;
a[cnt] = d;
nt[cnt] = h[u];
h[u] = cnt++;
}
int bfs()//计算边权为1的图，图上各点到源点的距离
{
memset(l,-1,sizeof(l));
memcpy(c,h,sizeof(h));//把h数组复制到c数组里
l[s] = 0;
c[s] = h[s];
queue<int> q;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = h[u];i != -1;i = nt[i])
{
if(a[i] > 0 && l[to[i]] == -1)
{
l[to[i]] = l[u] + 1;//深度+1
q.push(to[i]);
if(to[i] == t)
{
return 1;
}
}
}
}
return 0;
}
long long dfs(int u,long long f)
{
if(u == t)
{
return f;
}
long long x = f;//剩余流量
for(int i = c[u];i != -1 && x > 0;i = nt[i])
{
c[u] = i;//当前弧优化
if(a[i] > 0 && l[to[i]] == l[u] + 1)
{
long long w = dfs(to[i],min(a[i],x));
if(w == 0)//剪枝，去除增广完毕的点
{
l[to[i]] = -1;
}
x -= w;//剩余流量减少c
a[i] -= w;
a[i ^ 1] += w;
}
}
return f - x;//返回用了的水流
}
int main()
{
memset(h,-1,sizeof(h));
memset(nt,-1,sizeof(nt));
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i = 1;i <= m;i++)
{
int u,v;
long long w;
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);//建边
add(v,u,0);
}
long long ans = 0;
while(bfs() == 1)
{
ans += dfs(s,1e9);
}
printf("%lld",ans);
return 0;
}
```
这份代码的时间复杂度是$O(mn^2)$，因为边数往往大于顶点数，所以Dinic算法的时间复杂度小于EK算法。
------------
我们来总结一下：
**①时间复杂度**
FF：$O(m*ans)
EK：O(nm^2)
Dinic：O(mn^2)
②中心思想
FF：用dfs寻找增广路径，然后更新残存网络，直到找不到增广路径
EK：用bfs判断能否到达终点，能就累加到终点的水流，最后输出和
Dinic：先用bfs分层，再用dfs寻找
③用到的函数
FF：add、dfs
EK：add、bfs
Dinic：add、bfs、dfs
④应用场景
FF：当这个题数据很小时，可以用这个最简单的方法
EK：在n>m时通用，时间复杂度不高，也不麻烦
Dinic：数据很大，且m>n时
⑤优点和缺点
FF：代码简单，时间复杂度高
EK：时间复杂度比FF高、代码相对简单，但有些题还是过不去
Dinic：时间复杂度最低、常用，码量大
最后，附上参考的博客链接：知乎、博客园、CSDN