Dinic 28pts求条

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=207, M=5007;
int n, m, s, t;
int head[N], to[M<<1], nxt[M<<1], tot=1, now[N];
ll val[M<<1], dis[N];
ll ans=0;
queue<int> q;
void add(int u, int v, ll w){
    tot++;
    nxt[tot]=head[u];
    head[u]=tot;
    to[tot]=v;
    val[tot]=w;
}
int bfs(){
    memset(dis, 0x3f, sizeof(dis));
    while(q.size())
        q.pop();
    q.push(s);
    dis[s]=0;
    now[s]=head[s];
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(val[i]>0 && dis[v]==0x3f3f3f3f3f3f3f3f){
                q.push(v);
                now[v]=head[v];
                dis[v]=dis[u]+1;
                if(v==t)
                    return 1;
            }
        }
    }
    return 0;
}
int dfs(int x, ll flow){
    if(x==t || !flow)
        return flow;
    ll ans=0;
    for(int i=now[x];i && flow;i=nxt[i]){
        now[x]=i;
        int v=to[i];
        if(val[i]>0 && dis[v]==dis[x]+1){
            ll f=dfs(v, min(flow, val[i]));
            if(f==0)
                dis[v]=0x3f3f3f3f3f3f3f3f;
            val[i]-=f;
            val[i^1]+=f;
            ans+=f;
            flow-=f;
        }
    }
    return ans;
}
int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u, v;
        ll w;
        cin>>u>>v>>w;
        add(u, v, w);add(v, u, w);
    }
    while(bfs()) ans+=dfs(s, 0x3f3f3f3f3f3f3f3fLL);
    cout<<ans<<endl;
    return 0;
}

AC#9 #11 #12 其他WA