백준 6086번: 최대 유량 (C++)

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

6086번: 최대 유량

---

Solved By:  Edmonds-Karp

 

처음으로 최대 유량 문제를 풀어보았습니다. BFS를 활용한 Edmonds-Karp를 사용했습니다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define MAX ('z' - 'A' + 1)
#define INF 1e9
using namespace std;

int c[MAX][MAX];
int f[MAX][MAX];
vector<int> adj[MAX];
int parent[MAX];
int resultMaxFlow = 0;

int n;

// BFS를 활용하여 Edmonds-Karp
int maximumFlow(int source, int sink){
    while(true){
        memset(parent, -1, sizeof(parent));
        queue<int> q; //BFS Queue
        
        q.push(source);
        // BFS, 잔여 용량이 남아있는 것을 확인하며
        // sink로 갈 수 있는지 확인
        while(!q.empty()){
            int now = q.front();
            q.pop();
            
            for(int i = 0; i < adj[now].size(); i++){
                int next = adj[now][i];
                
                if((c[now][next] - f[now][next] > 0)
                && (parent[next] == -1)){
                    q.push(next);
                    parent[next] = now;
                    if(next == sink) break;
                }
            }
            // 이 BFS의 역할은 잔여용량 확인 후, sink를 갈 수 있느냐가
            // 관건임. sink만 탐색 되면 된다.
            if(parent[sink] != -1) break;
        }
        
        // BFS 탐색이 끝났는데 sink로 가는 경로가 없다는 것은
        // source에서 sink로 더 이상 갈 수 없다는 의미
        // >>종료
        if(parent[sink] == -1) break;
        
        int tempMaxFlow = INF;
        int residualCapacity; // 잔여 용량
        
        for(int i = sink; i != source; i = parent[i]){
            // source에서 sink로 온 경로를 보면서 (잔여 용량 확인)
            // 흘려보낼 수 있는 최대 유량을 최솟값 갱신을 통해 확인
            residualCapacity = c[parent[i]][i] - f[parent[i]][i];
            tempMaxFlow = min(tempMaxFlow, residualCapacity);
        }
        
        for(int i = sink; i != source; i = parent[i]){
            f[parent[i]][i] += tempMaxFlow;
            // 유량의 대칭성으로 인한 역간선 갱신
            f[i][parent[i]] -= tempMaxFlow;
        }
        
        resultMaxFlow += tempMaxFlow;
    }
    
    return resultMaxFlow;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        char a, b; int capacity;
        cin >> a >> b >> capacity;
        
        adj[a - 'A'].push_back(b - 'A');
        adj[b - 'A'].push_back(a - 'A');
        
        c[a - 'A'][b - 'A'] += capacity;
        c[b - 'A'][a - 'A'] += capacity;
    }
    
    cout << maximumFlow('A' - 'A', 'Z' - 'A');
    return 0;
}