6086 최대 유량 c++

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

 

주어진 파이프를 이용해 A -> Z 로의 최대 유량을 계산하는 문제입니다. 

주의할 점 : 소문자도 된다. 병렬로 연결도 가능하다. 양방향 연결이다. 

 

Edmonds Karp 알고리즘을 이용해 최대 유량을 계산하면 되지만, 양방향성과 병렬 가능에 주의를 해야 합니다. 

기본적으로는 가상의 역방향 엣지를 추가하고, cap은 0으로 유지하여 Edmonds-Karp 알고리즘을 수행하지만, 

양방향이므로, 역방향 엣지와 cap을 동일하게 잡아줍니다. 

그리고 병렬처리가 가능하므로 cap을 누적하여 추가해줍니다. 

 

불필요한 bfs 탐색을 방지하기 위해 vector에 누적해서 동일한 node를 추가하는 것 대신, set으로 연결된 노드를 관리하였습니다. 

 

최대 유량 계산 시 사용되는 역방향 유량은 양방향 그래프와 상관없이, 현재 체크된 증가 경로 상의 유량을 계산할 때 사용하는 것이므로, 동일하게 음수 처리를 해주어야 합니다. 

 

코드는 아래와 같습니다. 

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

int n;
int inf = 987654321; // 모든 엣지 다 통과해도 70만

set<int> graph[52]; // A : 0 ~ Z : 25, a : 26 ~ z : 51
// graph[i] : i와 연결된 노드 집합
int cap[52][52]; // [i][j] -> i to j capacity (해당 엣지 용량)
int flow[52][52]; // [i][j] -> i to j flow (현재까지 계산된 유량)

int A = 0; // source
int Z = 25; // sink

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

void init() {

    for(int i = 0; i < 52; i++) {
        for(int j = 0; j < 52; j++) {
            cap[i][j] = 0;
            flow[i][j] = 0;
        }
    }

    cin >> n;

    char c1, c2;
    int v, node1, node2;
    for(int i = 0; i < n; i++) {
        cin >> c1 >> c2 >> v;
        node1 = charToInt(c1);
        node2 = charToInt(c2);

        graph[node1].insert(node2);
        graph[node2].insert(node1); // 문제 상 양방향 그래프 

        cap[node1][node2] += v; // 병렬로 연결 가능하므로 누적해서 cap 추가 
        cap[node2][node1] += v;
    }
}

int calc(int source, int sink) {
    // edmonds-karp

    int res = 0;

    while(true) {
        // 증가 경로 없을 때까지 반복

        vector<int> parents(52, -1); // 증가 경로 상 부모 없으면 -1 
        queue<int> q; // 증가 경로 계산 시 사용될 큐 (bfs)

        parents[source] = source;
        q.push(source);

        while(!q.empty() && (parents[sink] == -1)) {
            // 다 돌거나 sink 증가 경로에 포함되면 종료 

            int cur = q.front();
            q.pop();

            // 잔여 용량 있고 증가 경로에 포함 안 된 경우, 증가 경로에 추가 
            for(auto next : graph[cur]) {
                int remain = cap[cur][next] - flow[cur][next];
                if((remain > 0) && (parents[next] == -1)) {
                    q.push(next);
                    parents[next] = cur;
                }
            }
        }

        // sink 증가 경로에 없음. 즉, 더 이상 증가 경로 없음 
        if(parents[sink] == -1) break;

        // 증가 경로 중 잔여 용량 최소값만큼 유량 추가 
        int node = sink;
        int p; // 부모 노드 계산용 
        int amount = inf;
        while(node != source) {
            p = parents[node];
            amount = min(amount, cap[p][node] - flow[p][node]);
            node = p;
        }

        // 계산된 유량 추가
        node = sink;
        while(node != source) {
            p = parents[node];
            flow[p][node] += amount;
            flow[node][p] -= amount; 
            node = p;
        }

        // 전체 유량에 추가 
        res += amount;
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    init();
    cout << calc(A, Z);
}