[BOJ-6086]최대유량

https://www.acmicpc.net/problem/6086

[문제풀이]

이미 그래프의 구성이 주어져 있고 source, sink가 정해져있기 때문에 그래프 모델링에 신경을 쓰지 않고 에드몬드카프 알고리즘을 바로 사용할 수 있던 문제였다.

[C++ source code]

#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
const int MAX_V = 111;
const int INF = 1 << 30;
 
int c[MAX_V][MAX_V];
int f[MAX_V][MAX_V];
int parent[MAX_V];
 
int residual(int here, int there) {
    return c[here][there] - f[here][there];
}
 
int min2(int a, int b) {
    return (a > b) ? b : a;
}
 
int ford_fulkerson(int source, int sink) {
    int total = 0;
    while (true) {
        memset(parent, -1, sizeof(parent));
        queue<int> Q;
        Q.push(source);
        parent[source] = source;
        while (!Q.empty()) {
            int here = Q.front();
            Q.pop();
            for (int there = 0; there < MAX_V; there++) {
                if (residual(here, there) > 0 && parent[there] == -1) { 
                    parent[there] = here;
                    Q.push(there);
                }
            }
        }
        
        if (parent[sink] == -1) break;
 
        int mn = INF;
        for (int p = sink; p != source; p = parent[p]) {
            mn = min2(c[parent[p]][p] - f[parent[p]][p], mn);
        }
 
        for (int p = sink; p != source; p = parent[p]) {
            f[parent[p]][p] += mn;
            f[p][parent[p]] -= mn;
        }
        total += mn;
    }
    return total;
}
 
int select_node(char V) {
    if ('A' <= V && V <= 'Z') {
        return V - 'A';
    }
    return V - 'a' + 26;
}
 
int main() {
    int n;
    char u, v;
    int capacity;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%*c%c%*c%c%*c%d", &u, &v, &capacity);
        c[select_node(u)][select_node(v)] += capacity;
    } // input
        
    int ans = ford_fulkerson(select_node('A'), select_node('Z'));
    printf("%d\n", ans);
    return 0;
}