2171. EK求最大流

2171. EK求最大流
EK算法，每次找一条路径,找到后立马返回
dinic,一次可以找多条路径

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int M=1e6+6;

int h[N],ne[M],e[M],w[M],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,S,T;
int d[N],pre[N];
bool vis[N];
bool bfs() {
    memset(vis,0,sizeof(vis));
    memset(pre,0,sizeof(pre));
    memset(d,0,sizeof(d));
    queue<int>q;
    q.push(S);
    vis[S]=1;
    d[S]=1e9;
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            if(vis[to]==0&&w[i]>0) {
                vis[to]=1;
                pre[to]=i;
                d[to]=min(w[i],d[now]);
                q.push(to);
                if(to==T)return 1;
            }
        }
    }
    return 0;
}

int EK() {
    int ans=0;
    while(bfs()) {
        ans+=d[T];
        for(int i=T;i!=S;i=e[pre[i]^1]) {
            int id=pre[i];
            w[id]-=d[T];
            w[id^1]+=d[T];
        }
    }
    return ans;
}

int main() {
    cin>>n>>m>>S>>T;
    while(m--) {
        int x,y,wi;
        cin>>x>>y>>wi;
        add(x,y,wi);
        add(y,x,0);
    }
    cout<<EK();
    return 0;
}