最大流模板Edmonds-Karp O(n*m^2)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 3;
const int INF = 0x3f3f3f3f;
ll n,head[maxn],minflow[maxn],pre[maxn],vis[maxn],tot,maxflow;
struct Edge {
    ll to,w,Next;
}edge[maxn*20];
void add(ll x,ll y,ll z)
{
    edge[++tot].to=y,edge[tot].w+=z,edge[tot].Next=head[x],head[x]=tot;
    edge[++tot].to=x,edge[tot].Next=head[y],head[y]=tot;
}
bool bfs(ll s,ll t)
{
    for(ll i=0;i<=n;i++) vis[i]=0;
    queue<ll> q;
    q.push(s); vis[s]=1,minflow[s]=INF;
    while(!q.empty())
    {
        ll x=q.front(),y; q.pop();
        for(ll i=head[x];i;i=edge[i].Next) {
            y=edge[i].to;
            if(edge[i].w&&!vis[y])
            {
                minflow[y]=min(minflow[x],edge[i].w);
                pre[y]=i,vis[y]=1;
                q.push(y);
                if(y==t) return true;
            }
        }
    }
    return false;
}
void update(ll s,ll t)
{
    ll now=t;
    while(now!=s) 
    {
        ll i=pre[now];
        edge[i].w-=minflow[t];
        edge[i^1].w+=minflow[t];
        now=edge[i^1].to;
    }
    maxflow+=minflow[t];
}
int main()
{
    ll m,s,t;
    while(~scanf("%lld%lld%lld%lld",&n,&m,&s,&t))
    {
        ll x,y,z;
        maxflow=0,tot=1;
        for(ll i=0;i<=n;i++) head[i]=pre[i]=minflow[i]=0;
        for(ll i=0;i<=max(n*2,m);i++) edge[i].w=edge[i].Next=0;
        for(ll i=1;i<=m;i++) {
            scanf("%lld%lld%lld",&x,&y,&z); 
            add(x,y,z);
        } 
        while(bfs(s,t)) update(s,t);
        printf("%lld\n",maxflow);
    }
    
    return 0;
}