6086 최대 유량

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int cost[60][60] = { 0 };
int flow[60][60] = { 0 };
vector<vector<int> > adj(60);
 
int ctoi(char c) {
    if (c < 'a')
        return (int)c - 'A' + 1;
    else
        return (int)c - 'a' + 26 + 1;
}
 
int main() {
    int n;
    scanf("%d", &n);
    getchar();
 
    for (int i = 1; i <= n; i++) {
        char a, b;
        int a1, a2, c;
        scanf("%c %c %d", &a, &b, &c);
        getchar();
 
        a1 = ctoi(a);
        a2 = ctoi(b);
        
        cost[a1][a2] += c;
        cost[a2][a1] += c;
 
        adj[a1].push_back(a2);
        adj[a2].push_back(a1);
    }
 
    int rst = 0;
    while (1) {
        queue<int> q;
        int visit[60] = { 0 };
        int prev[60] = { 0 };
 
        visit[1] = 1;
        q.push(1);
 
        int flag = 0;
        while (q.empty() == false) {
            int cur = q.front();
            q.pop();
 
            if (cur == 26) {
                flag = 1;
                break;
            }
 
            for (int i = 0; i < adj[cur].size(); i++) {
                int next = adj[cur][i];
 
                if (cost[cur][next] > flow[cur][next] && visit[next] == 0) {
                    visit[next] = 1;
                    q.push(next);
 
                    prev[next] = cur;
                }
            }
        }
        if (flag == 0)
            break;
 
        int end = 26;
        int start = prev[end];
        int minFlow = cost[start][end] - flow[start][end];
        while (start != 1) {
            start = prev[start];
            end = prev[end];
 
            minFlow = min(minFlow, cost[start][end] - flow[start][end]);
        }
 
        end = 26;
        start = prev[end];
        flow[start][end] += minFlow;
        flow[end][start] -= minFlow;
        while (start != 1) {
            start = prev[start];
            end = prev[end];
            flow[start][end] += minFlow;
            flow[end][start] -= minFlow;
        }
 
        rst += minFlow;
    }
 
    printf("%d", rst);
}