[백준 6086번] [네트워크 플로우] 최대 유량

전형적인 네트워크 플로우 문제이다.

 

다만.. 조건을 꼼꼼하게 읽지 않아서 대문자와 소문자가 구분되는지를 놓쳤고, 그로 인해 단순하게 대문자 A ~ Z까지의 최대 유량을 구하는 문제인줄 알았다.

 

또한 추가적으로 이 문제에서 교훈이 있는데, 단순 그래프가 아닐 경우에는 capacity를 계산할 때 += 처리를 해주어야 한다는 것이다.

이 지점만 주의해주면 된다.

 

코드 자체는 종만북에 있는 에드몬드 카프 알고리즘 코드를 차용하였다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define INF 987654321;

using namespace std;
typedef long long ll;

int ARR_NUM;
int capacity[52][52]; int flow[52][52];

int networkFlow(int source, int sink){
    memset(flow, 0, sizeof(flow));
    int totalFlow = 0;
    while(true){
        vector<int> parent(52, -1);
        queue<int> q;
        parent[source] = source;
        q.push(source);
        while(!q.empty() && parent[sink] == -1){
            int here = q.front(); q.pop();
            for(int there = 0; there < 52; there++){
                if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1){
                    q.push(there);
                    parent[there] = here;
                }
            }
        }
        if(parent[sink] == -1) break; // 더이상 증가하는 경로가 없는 경우

        int amount = INF;
        for(int p = sink; p != source; p = parent[p]){
            amount = min(amount, capacity[parent[p]][p] - flow[parent[p]][p]);
        }

        for(int p = sink; p != source; p = parent[p]){
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
        
        totalFlow += amount;
    }
    return totalFlow;
}

int change_index(char x){
    if('a' <= x && x <= 'z'){
        return x - 'a' + 26;
    }
    return x - 'A';
}

int main(void){
    fastio;
    memset(capacity, 0, sizeof(capacity));
    cin >> ARR_NUM;

    for(int i = 0; i < ARR_NUM; i++){
        char start, end;
        int capacity_temp;
        cin >> start >> end >> capacity_temp;
        int start_index = change_index(start);
        int end_index = change_index(end);
        capacity[start_index][end_index] += capacity_temp;
        capacity[end_index][start_index] += capacity_temp;
    }

    cout << networkFlow(0, 25) << "\n";

    return 0;
}