首页 > > 程序设计 > C/C++ >

浅谈最大流的Dinic算法

2018-06-17 21:17:44来源：未知阅读 ()

PART 1 什么是网络流

网络流(network-flows)是一种类比水流的解决问题方法，与线性规划密切相关。网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。【引自百度百科】

PART 2 一些概念

容量网络:设G(V,E),是一个有向网络,在V中指定了一个顶点,称为源点(记为Vs),以及另一个顶点,称为汇点(记为Vt);对于每一条弧<u,v>属于E,对应有一个权值c(u,v)>0,称为弧的容量.通常吧这样的有向网络G称为容量网络.

弧的流量:通过容量网络G中每条弧<u,v>,上的实际流量(简称流量),记为f(u,v);

最大流:在容量网络中,满足弧流量限制条件,且满足平衡条件并且具有最大流量的可行流,称为网络最大流,简称最大流.

增广路:

设f是一个容量网络G中的一个可行流,P是从Vs到Vt 的一条链,若P满足以下条件:

a.P中所有前向弧都是非饱和弧,

b.P中所有后向弧都是非零弧.

则称P为关于可行流f 的一条增广路.

沿这增广路改进可行流的操作称为增广.

残留容量:给定容量网络G(V,E),及可行流f,弧<u,v>上的残留容量记为cl(u,v)=c(u,v)-f(u,v).每条弧上的残留容量表示这条弧上可以增加的流量.因为从顶点u到顶点v的流量减少,等效与从顶点v到顶点u的流量增加,所以每条弧<u,v>上还有一个反方向的残留容量cl(v,u)=-f(u,v).

残留网络:设有容量网络G(V,E)及其上的网络流f,G关于f的残留网络记为G(V',E').其中G'的顶点集V'和G中顶点集G相同,V'=V.对于G中任何一条弧<u,v>,如果f(u,v)<c(u,v),那么在G'中有一条弧<u,v>属于E',其容量为c'(u,v)=c(u,v)-f(u,v),如果f(u,v)>0,则在G'中有一条弧<v,u>属于E',其容量为c'(v,u)=f(u,v).残留网络也称为剩余网络。

PART 3 Dinic算法的基本思路:

1.根据残量网络计算层次图。

2.在层次图中使用DFS进行增广直到不存在增广路

3.重复以上步骤直到无法增广

PART 4 代码简介

1.用链式前向星存储图

2.用bfs将图分层

3.用dfs进行增广

PART 5 模板（洛谷p3376）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int inf=1e9+7;
struct edge{
      int c,to,next;
}e[210000];
int head[11000],cnt,level[11000],cur[11000];
inline void read(int &x){
      int f=1;x=0;
      char s=getchar();
      while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
      while(s>='0'&&s<='9'){x=x*10+(s-'0');s=getchar();}
      x=(f==1?x:-x);
}
inline void add(int u,int v,int w){
      e[cnt].to=v;
      e[cnt].c=w;
      e[cnt].next=head[u];
      head[u]=cnt++;
}
inline int bfs(int s,int t){
      memset(level,-1,sizeof(level));
      queue<int>q;
      q.push(s);
      level[s]=0;
      while(!q.empty()){
          int u;
          u=q.front();
          q.pop();
        for(int i=head[u];~i;i=e[i].next){
           int v=e[i].to;
           if(level[v]==-1&&e[i].c){
             level[v]=level[u]+1;
             if(v==t)return 1;
             q.push(v);
           }
        }
      }
    return 0;
}
inline int dfs(int u,int v,int flow){
      if(u==v)return flow;
      int res=0;
      if(!cur[u])cur[u]=head[u];
      for(int i=cur[u];~i;i=e[i].next){
          cur[u]=i;//当前弧优化
          int j=e[i].to;
          if(level[j]==level[u]+1&&e[i].c){
              int f=dfs(j,v,min(flow-res,e[i].c));//多路增广优化 
              res+=f;
              e[i].c-=f;
              e[i^1].c+=f;
          }
      }
      if(!res)level[u]=-1;//炸点优化 
      return res;
}
int main()
{     int n,m,i,j,k,u,w,v,s,t,ans=0;
      read(n),read(m),read(s),read(t);
      memset(head,-1,sizeof(head));
      for(i=1;i<=m;i++){
         read(u),read(v),read(w);
         add(u,v,w);
         add(v,u,0);
      }
      while(bfs(s,t)){
        memset(cur,0,sizeof(cur));
        while(int a=dfs(s,t,inf))
          ans+=a;
      }
      printf("%d\n",ans);
      return 0;
}