Max Flow Sample Code

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 987654321
using namespace std;

int n, c[52][52], f[52][52];
vector<int> a[52];

int ctoi(char c)
{
    if (c >= 'a' && c <= 'z')
        return c - 'a';
    else
        return c - 'A' + 26;
}

// Edmond Karp (BFS)
void network_flow()
{
    int total = 0, s = ctoi('A'), t = ctoi('Z');
    while (true)
    {
        int prev[52];
        memset(prev, -1, sizeof(prev));
        queue<int> q;
        q.push(s);
        while (!q.empty() && prev[t] == -1)
        {
            int now = q.front();
            q.pop();
            for (int next : a[now])
            {
                if (c[now][next] - f[now][next] > 0 && prev[next] == -1)
                {
                    q.push(next);
                    prev[next] = now;
                    if (next == t)
                        break;
                }
            }
        }

        if (prev[t] == -1)
            break;

        int flow = INF; // 증가경로 중에 최소값
        for (int i = t; i != s; i = prev[i])
            flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);
        for (int i = t; i != s; i = prev[i])
        {
            f[prev[i]][i] += flow; // 정방향 +
            f[i][prev[i]] -= flow; // 역방향 -
        }
        total += flow;
    }
    printf("%d\n", total);
}

int main()
{
    scanf("%d", &n);
    while (n--)
    {
        char u, v;
        int w;
        scanf(" %c %c %d", &u, &v, &w);
        u = ctoi(u);
        v = ctoi(v);
        c[u][v] += w;
        c[v][u] += w;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    network_flow();
    return 0;
}