P3376 【模板】网络最大流

P3376 【模板】网络最大流

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=205;
const int M=5005;

int h[N],ne[M<<1],e[M<<1],w[M<<1],tot=1;
void add(int from,int to,int wi) {
    e[++tot]=to;
    w[tot]=wi;
    ne[tot]=h[from];
    h[from]=tot;
}

int n,m,st,ed;
int cur[N],dep[N];

bool bfs() {
    for(int i=1;i<=n;i++)cur[i]=h[i],dep[i]=0;
    queue<int>q;
    q.push(st);
    dep[st]=1;
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            if(dep[to]==0&&w[i]>0) {
                q.push(to);
                dep[to]=dep[now]+1;
            }
        }
    }
    return dep[ed];
}

//sum是流过该点的流量
//ans也就上记录的答案
int dfs(int now,int sum) {
    if(now==ed)return sum;
    int ans=0;
    for(int i=cur[now];i&&sum;i=ne[i]) {//这个点还有流量
        cur[now]=i;
        int to=e[i];
        if(w[i]>0&&(dep[to]==dep[now]+1)) {
            int k=dfs(to,min(sum,w[i]));//从这个点流下去不行了，进行一下剪枝
            if(k==0)dep[to]=0;
            w[i]-=k;
            w[i^1]+=k;
            ans+=k;
            sum-=k;
        }
    }
    return ans;
}

signed main() {
    cin>>n>>m>>st>>ed;
    while(m--) {
        int x,y,wi;
        cin>>x>>y>>wi;
        add(x,y,wi);
        add(y,x,0);//反向边提供后悔的操作
    }
    int ans=0;
    while(bfs())ans+=dfs(st,1e9);
    cout<<ans;
    return 0;
}