想象这样一个场面：从自来水厂到你家有若干根水管，每根水管都有一个流量上限，你想要求出到你家的水流量最大是多少。
这就是经典的网络最大流问题。
在详细介绍最大流的解法前，让我们先认识一个概念，增广路。
何谓增广路？指的就是一条从源点（水厂）到汇点（家）的一条路径，这条路径可以使流到你家的水量增加。
我们求解最大流问题，自然就是不停找增广路的过程。可以证明，如果图中没有增广路，那么当前的流就是最大流。
Part 1 Edmond-Karp(EK)算法
怎样找增广路呢？采用 DFS 的方法很显然会被卡掉。
于是我们可以采用 BFS 的方法来找增广路，这就是EK算法。
EK 算法的过程很好理解：每次 BFS 寻找增广路，找不到增广路就结束。
但这样会产生一个问题：万一增广的时候出了错导致丢失了最优解的时候，该如何解决呢？
解决方法是加入反向边，给一个后悔的机会。
每次进行增广的过程时，我们不但要给当前边的流量减去 \(w\)，还要给它的反向边加上 \(w\)。
这样，我们就可以通过反向边，迂回地进行增广。
代码很简单：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
int v,w,next;
}e[200005];
struct node
{
int v,e;
}p[10005];
int head[10005],vis[10005];
int n,m,s,t,cnt=1;
void addedge(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
bool bfs()
{
queue<int> q;
memset(p,0,sizeof(p));
memset(vis,0,sizeof(vis));
vis[s]=1;
q.push(s);
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int i=head[cur];i;i=e[i].next)
if((!vis[e[i].v])&&e[i].w)
{
p[e[i].v].v=cur;
p[e[i].v].e=i;
if(e[i].v==t)return 1;
vis[e[i].v]=1;
q.push(e[i].v);
}
}
return 0;
}
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);
addedge(u,v,w);
addedge(v,u,0);
}
int ans=0;
while(bfs())
{
int minw=INF;
for(int i=t;i!=s;i=p[i].v)
minw=min(minw,e[p[i].e].w);
for(int i=t;i!=s;i=p[i].v)
{
e[p[i].e].w-=minw;
e[p[i].e^1].w+=minw;
}
ans+=minw;
}
printf("%d\n",ans);
return 0;
}
如果我们设点数为 \(n\)，边数为 \(m\)，EK 算法的时间复杂度是 \(O(nm^2)\)，这样的效率已经足以解决大多数问题，但我们还有效率更高的方法。
Part 2 Dinic算法
相对于EK算法的 \(O(nm^2)\) 的时间复杂度，Dinic 算法的复杂度乍一看似乎并不算太优秀：\(O(n^2m)\)。
没错，在稀疏图上两者确实没有太大差异，但稠密图上，Dinic 算法的实际运行效率要高很多。
（事实上，如果没有下文提到的多路增广和当前弧优化，Dinic 的实际运行效率甚至不如 EK 算法）
每次增广前，我们先用 BFS 来将图分层。设源点的层数为 \(0\)，那么一个点的层数便是它离源点的最近距离。
通过分层，我们可以干两件事情：
- 如果不存在到汇点的增广路（即汇点的层数不存在），我们即可停止增广。
- 让我们能找到一条最短的增广路。
与 EK 不同，在 Dinic 中，我们采用 DFS 来找增广路。
我们每次找增广路的时候，都只找比当前点层数多 \(1\) 的点进行增广（这样就可以确保我们找到的增广路是最短的）。
Dinic 增广时的一大优势就是：多路增广。
每次找到一条增广路的时候，如果残余流量没有用完怎么办呢？当然不能浪费！我们可以利用残余部分流量，再找出一条增广路。这样便大大提高了算法的效率。
我们还能发现一个事实：如果一条边已经被增广过，那么它就没有可能被增广第二次。
那么，我们下一次进行增广的时候，就可以不必再走那些已经被增广过的边。这就是当前弧优化。
通过当前弧优化，Dinic 的实际运行效率又能够提高一大截。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
int v,w,next;
}e[200005];
int n,m,s,t,cnt=1;
int head[100005],dep[100005],vis[100005],cur[100005];
void addedge(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
bool bfs()
{
queue<int> q;
memset(dep,INF,sizeof(dep));
memset(vis,0,sizeof(vis));
memcpy(cur,head,sizeof(head));
dep[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
int p=q.front();
q.pop();
vis[p]=0;
for(int i=head[p];i;i=e[i].next)
if(dep[e[i].v]>dep[p]+1&&e[i].w)
{
dep[e[i].v]=dep[p]+1;
if(!vis[e[i].v])
{
vis[e[i].v]=1;
q.push(e[i].v);
}
}
}
if(dep[t]==INF)return 0;
return 1;
}
int dfs(int p,int w)
{
if(p==t)return w;
int used=0;//已经使用的流量
for(int i=cur[p];i;i=e[i].next)//每条边都尝试找一次增广路
{
cur[p]=i;//当前弧优化
if(dep[e[i].v]==dep[p]+1&&e[i].w)
{
int flow=dfs(e[i].v,min(w-used,e[i].w));
if(flow)
{
used+=flow;
e[i].w-=flow;
e[i^1].w+=flow;
if(used==w)break;//残余流量用尽了就停止增广
}
}
}
return used;
}
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);
addedge(u,v,w);
addedge(v,u,0);
}
int ans=0;
while(bfs())
ans+=dfs(s,INF);
printf("%d\n",ans);
return 0;
}
PS：在求解二分图最大匹配的时候，可以证明 Dinic 算法的复杂度上限为\(O(m \sqrt n)\)，比匈牙利算法的复杂度上限 \(O(nm)\) 要优。（实际效率来说，匈牙利算法也很不错）
Part 3 ISAP
（先咕着）