Dinic算法

算法：Dinic算法
问题：最大流问题
输入：带权有向图，源点，汇点
输出：最大流的值
备注：进行了当前弧优化，复杂度

#include<bits/stdc++.h>
using namespace std;
const int maxn=200+1;
const int maxm=5000+1;
typedef long long LL;
const LL INF=0x7fffffffffffffff;

// data structure
struct node{
    int to,nxt;
    LL w;
}edge[2*maxm];

int head[maxn],tot;

void init_edge(int n){
    for(int i=1;i<=n;i++)
        head[i]=-1;
    tot=0;
}

void add_edge(int u,int v,LL w){
    edge[tot]=(node){v,head[u],w};
    head[u]=tot++;
    edge[tot]=(node){u,head[v],0};
    head[v]=tot++;
}

// dinic's resources
int n,m,src,tar;
int dis[maxn],que[maxn],cur[maxn];

int build(){
    int l=0,r=0;
    for(int i=1;i<=n;i++)
        dis[i]=0;
    dis[src]=1;
    que[r++]=src;
    while(l<r){
        int u=que[l++];
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            int v=edge[i].to;
            if(edge[i].w && !dis[v]){
                dis[v]=dis[u]+1;
                que[r++]=v;
            }
        }
    }
    return dis[tar];
}

LL find(int u,LL in){
    if(u==tar) return in;
    LL out=0;
    for(int i=cur[u];i!=-1;i=edge[i].nxt){
        // promote
        cur[u]=i;
        int v=edge[i].to;
        if(edge[i].w && dis[v]==dis[u]+1){
            LL f=find(v,min(in,edge[i].w));
            if(f){
                in-=f;
                edge[i].w-=f;
                edge[i^1].w+=f;
                out+=f;
                if(!in) return out;
            }
        }
    }
    return out;
}

LL dinic(){
    LL maxflow=0;
    while(build()){
        for(int i=1;i<=n;i++) cur[i]=head[i];
        maxflow+=find(src,INF);
    }
    return maxflow;
}


int main(){
    scanf("%d%d%d%d",&n,&m,&src,&tar);
    init_edge(n);
    for(int i=1;i<=m;i++){
        int u,v;
        LL w;
        scanf("%d%d%lld",&u,&v,&w);
        add_edge(u,v,w);
    }
    LL ans=dinic();
    printf("%lld\n",ans);
    return 0;
}

参考资料：https://www.cnblogs.com/ticmis/p/13211009.html