最大流：Dinic算法-白红宇

最大流：Dinic算法

阅读量：4311 次

发布时间：2019-06-06

本文共 1706 字，大约阅读时间需要 5 分钟。

蒟蒻居然今天第一次写网络流我太弱啦！

最大流问题有很多解法虽然isap常数巨小但是连dinic都写挂的本蒟蒻并不会orz

那么我们选用比较好实现的dinic来解决最大流问题

来一段定义：

于是我们就可以这样实现啦！

#pragma GCC optimize("O2")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #define N 100001typedef long long ll;const int inf=0x3fffffff;const int maxn=2017;using namespace std;inline int read(){ int f=1,x=0;char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch<='9'&&ch>='0') { x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); } return f*x;}struct tsdl{ int w,to,next;} edge[N*4];int dis[N],head[N],q[N],tot,astart,aend;void add(int ui,int vi,int wi){ edge[tot].next=head[ui]; edge[tot].w=wi; edge[tot].to=vi; head[ui]=tot++;}int m,n;bool bfs(){ queue
                
                 q; memset(dis,0,sizeof(dis)); dis[astart]=1; q.push(astart); while(!q.empty()) { int x=q.front(); q.pop(); for(int i=head[x];i!=-1;i=edge[i].next) { if(edge[i].w&&!dis[edge[i].to]) { dis[edge[i].to]=dis[x]+1; q.push(edge[i].to); } } } if(dis[aend])return 1; return 0;}int dfs(int u,int lim){ if(u==aend||!lim)return lim; int ret=0; for(int i=head[u];i!=-1;i=edge[i].next) { if(dis[edge[i].to]==dis[u]+1) { int f=dfs(edge[i].to,min(edge[i].w,lim)); edge[i].w-=f; edge[i^1].w+=f; lim-=f,ret+=f; } } if(!ret)dis[u]=-1; return ret;}int main(){ memset(head,-1,sizeof(head)); int ans=0; n=read(),m=read(),astart=read(),aend=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); add(u,v,w); add(v,u,0); } while(bfs())ans+=dfs(astart,inf); printf("%d\n",ans);}