算法记录-9-（Dinic算法-最大流）

时间复杂度：O(n^2m)
Dinic是比较容易实现的效率最高的网络流算法之一，一般能够处理10^4~10^5规模的网络

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
const int inf=1<<29,N=50010,M=300010;
int head[N],ver[M],edge[M],Next[M],d[N],now[M];
int n,m,s,t,tot,maxflow;
queue<int> q;
void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
    ver[++tot]=x,edge[tot]=0,Next[tot]=head[y],head[y]=tot;
}
bool bfs(){
    memset(d,0,sizeof d);
    while(q.size())    q.pop();
    q.push(s);d[s]=1;now[s]=head[s];
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=Next[i]){
            if(edge[i]&&!d[ver[i]]){
                q.push(ver[i]);
                now[ver[i]]=head[ver[i]];
                d[ver[i]]=d[x]+1;
                if(ver[i]==t)    return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if(x==t)    return flow;
    int rest=flow,k,i;
    for(i=now[x];i&&rest;i=Next[i])
        if(edge[i]&&d[ver[i]]==d[x]+1){
            k=dinic(ver[i],min(rest,edge[i]));
            if(!k)    d[ver[i]]=0;
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
        }
    now[x]=i;
    return flow-rest;
}
int main(){
    cin>>n>>m;
    cin>>s>>t;
    tot=1;
    for(int i;i<=m;i++){
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);
    }
    int flow=0;
    while(bfs())
        while(flow=dinic(s,inf))    maxflow+=flow;
    cout<<maxflow;
    return 0;    
}