dinic算法68pts求调

代码如下

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const ll N = 10007, M = 100007, INF = LLONG_MAX;
struct node{
    ll to, val, nxt;
}e[M << 1]; 
ll n, m, S, T, tot;
ll head[N], d[N], cur[N];
queue<int> q;

void add(int u, int v, int w){
    e[tot].to = v, e[tot].val = w, e[tot].nxt = head[u], head[u] = tot++;
    e[tot].to = u,e[tot].val = 0, e[tot].nxt = head[v], head[v] = tot++;
}
bool bfs(){
    while(!q.empty()) q.pop();
    memset(d, -1,sizeof d);
    q.push(S), d[S] = 0, cur[S] = head[S];
    while(!q.empty()){
        int t = q.front();
        q.pop();
        for(ll i = head[t]; ~i; i = e[i].nxt){
            ll v = e[i].to;
            if(d[v] == -1 && e[i].val){
                d[v] = d[t] + 1;
                cur[v] = head[v];
                if(v == T) return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(ll u, ll limit){
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = e[i].nxt){
        cur[u] = i;
        ll v = e[i].to;
        if(d[v] == d[u] + 1 && e[i].val){
            ll t = find(v, min(e[i].val, limit - flow));
            if(!t) d[v] = -1;
            e[i].val -= t, e[i ^1].val += t, flow += t;
        }
    }
    return flow;
}
ll dinic(){
    int r = 0, flow;
    while(bfs()){
        while(flow = find(S,INF))
            r += flow;
    }
    return r;
}
int main(){
    scanf("%lld%lld%lld%lld", &n, &m, &S, &T);
    memset(head, -1, sizeof head);
    while(m--){
        ll a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        add(a, b, c);
    }
    printf("%lld\n", dinic());
    return 0;
}```