3396: [Usaco2009 Jan]Total flow 水流 (最大流)

#include
#include
#include
#define inf 0x7fffffff
using namespace std;

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 * 10 + ch - '0';
        ch = getchar();
    }
    return x*f;
}

struct edge {
    int to, next, v;
} e[50001];
int n, cnt = 1, ans, T = 801, head[50001], h[50001];

void insert(int u, int v, int w) {
    e[++cnt] = (edge){v, head[u], w};
    head[u] = cnt;
    e[++cnt] = (edge){u, head[v], 0};
    head[v] = cnt;
}

inline bool bfs() {
    int q[50001], t = 0, w = 0;
    memset(h, -1, sizeof (h));
    h[0] = 0;
    while (t <= w) {
        int now = q[t++];
        for (int i = head[now]; i; i = e[i].next) {
            if (e[i].v && h[e[i].to] == -1) {
                h[e[i].to] = h[now] + 1;
                q[++w] = e[i].to;
            }
        }
    }
    if (h[T] == -1)return 0;
    else return 1;
}

inline int dfs(int x, int f) {
    if (x == T)return f;
    int rest, used = 0;
    for (int i = head[x]; i; i = e[i].next) {
        if (e[i].v && h[e[i].to] == h[x] + 1) {
            rest = f - used;
            rest = dfs(e[i].to, min(e[i].v, rest));
            e[i].v -= rest;
            e[i ^ 1].v += rest;
            used += rest;
            if (used == f)return f;
        }
    }
    if (!used)h[x] = -1;
    return used;
}

void dinic() {
    while (bfs())ans += dfs(0, inf);
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        char ch[2];
        int a, b, c;
        scanf("%s", ch);
        a = ch[0] - 'A' + 1;
        scanf("%s", ch);
        b = ch[0] - 'A' + 1;
        c = read();
        insert(a, b, c);
    }
    insert(0, 1, inf);
    insert(26, T, inf);
    dinic();
    printf("%d", ans);
    return 0;
}