《关于我的dinic爆炸而且我还菜的不会调这档事》

RT

#include<bits/stdc++.h>
using namespace std;

int n,m,s,t,cnt=1,first[10010],nxt[200010],to[200010],w[200010];
bool vst[100010];

void add(int u,int v,int w2) {
    cnt++;
    w[cnt]=w2;
    to[cnt]=v;
    nxt[cnt]=first[u];
    first[u]=cnt;
}

int dep[10010];

bool bfs() {
    memset(dep,0,sizeof(dep));
    queue<int>q;
    q.push(1);
    dep[s]=1;
    while(!q.empty()) {
        int head=q.front();
        q.pop();
        for(int e=first[head];e;e=nxt[e]) {
            int v=to[e];
            if(!dep[v]&&w[e]) {
                dep[v]=dep[head]+1;
                q.push(v);
            }
        }
    }
    return dep[t];
}

int dinic(int now,int flow) {
    if(now==t) {
        return flow;
    }
    int out=0;
    for(int e=first[now];e&&flow;e=nxt[e]) {
        int v=to[e];
        if((dep[v]==dep[now]+1)&&(w[e])) {
            int outnow=dinic(v,min(w[e],flow));
            flow-=outnow;
            w[e]-=outnow;
            w[e^1]+=outnow;
            out+=outnow;
        }
    }
    if(out==0) dep[now]=0;
    return out;
}

int main() {
    int ans=0;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++) {
        int u2,v2,w2;
        cin>>u2>>v2>>w2;
        add(u2,v2,w2);
        add(v2,u2,0);
    }
    while(bfs()) {
        ans+=dinic(s,2e9);
    }
    cout<<ans;
}