网络流精讲——最大流 包教包会

先上代码，晚上再更。

//模板：网络最大流 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
const int INF=0x7fffffff;
struct node{
    int nxt;
    int to;
    int value;
}edge[maxn*3];
int head[maxn],cnt=-1;
int m,n,s,t;
int x,y,z;
void add(int x,int y,int z){
    edge[++cnt].nxt=head[x];
    edge[cnt].to=y;
    edge[cnt].value=z;
    head[x]=cnt;
}
queue<int> q;
int dep[maxn];
bool bfs(){//bfs建分层图 
    while(!q.empty()){
        q.pop();
    }//清空原有队列，从头再来 
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    q.push(s);
    while(!q.empty()){//同广搜 
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            int v=edge[i].to;
            if((edge[i].value>0)&&(dep[v]==0)){
                dep[v]=dep[u]+1;
                q.push(v); 
            }
        }
    }
    if(dep[t]>0) return 1;
    else return 0;//汇点没有深度了，不能再跑了 
}
int dfs(int now,int flow){
    if(now==t) return flow;//到达汇点，直接返回当前流量 
    for(int i=head[now];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if((dep[v]==dep[now]+1)&&(edge[i].value!=0)){
            int dic=dfs(v,min(flow,edge[i].value));//找到那个满足条件的流 
            if(dic>0){
                edge[i].value-=dic;//减去流量 
                edge[i^1].value+=dic;//反向边加，还可以有反悔
                return dic; 
            } 
        }//满足分层图并且可以走 
    }
    return 0;//如果在此结束，说明无增广路，bye-bye 
} 
int dinic(){
    int ans=0;
    while(bfs()){
        while(int cnm=dfs(s,INF)){
            ans+=cnm;//玄学的力量 
        }
    }    
    return ans;
} 
int main(){
    memset(head,-1,sizeof(head));
    memset(edge,-1,sizeof(edge));
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,0);
    }
    printf("%d
",dinic());
    return 0;
}