网络流学习笔记

/* %%%sweetdong123 */
/* %%%xyyxyyx */
/* %%%chenmingyu2002 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
 
using namespace std;
typedef long long LL;
const int MAXN = 100 + 10, MAXM = 5e3 + 10;
const LL INF = 1e17;
 
inline LL in()
{
    LL x = 0, flag = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * flag;
}

int n, m, s, t;

int nume, head[MAXN];
struct Adj { int nex, to; LL w; } adj[MAXM << 1];
void addedge(int from, int to, LL w)
{
    adj[nume] = (Adj) { head[from], to, w };
    head[from] = nume ++;
}

int level[MAXN], cur[MAXN];
queue <int> q;
bool BFS()
{
    while (!q.empty()) q.pop();
    memset(level, 0, sizeof level);
    level[s] = 1;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (int i = head[u]; i != -1; i = adj[i].nex)
        {
            int v = adj[i].to;
            if (adj[i].w > 0 && !level[v]) 
            {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t];
}
LL augment(int u, LL minf)
{
    if (u == t) return minf;
    LL nowf = 0;
    for (int & i = cur[u]; i != -1; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (level[v] == level[u] + 1 && adj[i].w > 0)
        {
            LL nexf = augment(v, min(minf - nowf, adj[i].w));
            adj[i].w -= nexf;
            adj[i ^ 1].w += nexf;
            nowf += nexf;
            if (nowf == minf) break;
        }
    }
    return nowf;
}
LL Dinic()
{
    LL ans = 0;
    while (BFS())
    {
        for (int i = 1; i <= n; ++ i) cur[i] = head[i];
        ans += augment(s, INF);
    }
    return ans;
}

int main()
{
    n = in(), m = in(), s = in(), t = in();
    memset(head, -1, sizeof head);
    for (int i = 1; i <= m; ++ i)
    {
        int u = in(), v = in(); LL c = in();
        addedge(u, v, c);
        addedge(v, u, 0);
    }
    printf("%lld
", Dinic());
    return 0;
}