网络流学习笔记——最大流

想象这样一个场面:从自来水厂到你家有若干根水管,每根水管都有一个流量上限,你想要求出到你家的水流量最大是多少。

这就是经典的网络最大流问题。

在详细介绍最大流的解法前,让我们先认识一个概念,增广路

何谓增广路?指的就是一条从源点(水厂)到汇点(家)的一条路径,这条路径可以使流到你家的水量增加。

我们求解最大流问题,自然就是不停找增广路的过程。可以证明,如果图中没有增广路,那么当前的流就是最大流。

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(n^2m)\),这样的效率已经足以解决大多数问题,但我们还有效率更高的方法。

Part 2 Dinic算法

相对于EK算法的\(O(n^2m)\)的时间复杂度,Dinic算法的复杂度乍一看似乎并不算太优秀:\(O(nm^2)\)。

没错,在稀疏图上两者确实没有太大差异,但稠密图上,Dinic算法的实际运行效率要高很多。

(事实上,如果没有下文提到的多路增广和当前弧优化,Dinic的实际运行效率甚至不如EK算法)

每次增广前,我们先用bfs来将图分层。设源点的层数为0,那么一个点的层数便是它离源点的最近距离。

通过分层,我们可以干两件事情:

  1. 如果不存在到汇点的增广路(即汇点的层数不存在),我们即可停止增广。
  2. 让我们能找到一条最短的增广路。

与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(n \sqrt{m})\),比匈牙利算法的复杂度上限\(O(nm)\)要优。(实际效率来说,匈牙利算法也很不错)

Part 3 ISAP

(先咕着)

发表评论

电子邮件地址不会被公开。 必填项已用*标注