Dinic 模板求调

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N = 2e2 + 50;
const int M = 5e3 + 50;
const int Mod = 1e9 + 7;
const int Inf = 0x3f3f3f3f;

#define int long long

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int n, m, s, t;

struct edge
{
    int to, nxt, dis;
} e[M << 1];

int head[N], cnt = 1;

void add_edge(int u, int v, int w)
{
    ++cnt;
    e[cnt].to = v;
    e[cnt].dis = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

int ans = 0;

int dis[N];

int cur[N];

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

int dinic(int u, int sum)
{
    if (u == t)
        return sum;
    int res = 0;
    for (int i = cur[u]; i && sum; i = e[i].nxt)
    {
        cur[u] = i;
        int v = e[i].to;
        if (e[i].dis > 0 && (dis[v] == dis[u] + 1))
        {
            int k = dinic(v, min(sum, e[i].dis));
            if (k == 0)
                dis[v] = Inf;
            e[i].dis -= k;
            e[i ^ 1].dis += k;
            res += k;
            sum -= k;
        }
    }
    return res;
}

signed main()
{
    n = read(), m = read(), s = read(), t = read();
    for (int i = 1; i <= m; ++i)
    {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
        add_edge(v, u, 0);
    }
    while (bfs())
    {
        for (int i = 1; i <= n; ++i)
            cur[i] = head[i];
        int flow = 0;
        while (flow = dinic(s, Inf))
            ans += flow;
    }
    printf("%lld\n", ans);
    return 0;
}