[백준 6086 | 포드 풀커슨] 최대 유량

 

풀이

 

네트워크 유량과 관련된 기본적인 문제로, BFS를 사용하는 포드-풀커슨 알고리즘을 사용하여 구현하였습니다. 포드-풀커슨 알고리즘을 사용하여 이 문제를 해결 할 때의 주의점은, 파이프가 양쪽 모두로 물을 흘려보낼 수 있으므로, 파이프 하나를 양방향 간선으로 취급해야 한다는 점과, 동일한 파이프가 2개 이상 주어질 수 있다는 점입니다.

 

즉, A->B로 가는 용량 5짜리 파이프와 용량 2짜리 파이프가 동시에 입력될 수 있는데, 둘 중 어느 하나를 선택하는 것이 아니라 두 용량 모두를 더한 것이 A->B로 가는 파이프의 최종 용량이라는 것입니다. 

 

 

소스 코드 (JAVA)

 

import java.util.*;
import java.io.*;

/*
    @sckimynwa
 */

public class BOJ_6086 {

    static int[][] capacity, flow;

    public static int atoi(char c) {
        if('A' <= c && c <= 'Z') return (c - 65);
        else if('a'<=c && c<='z')  return (c - 71);
        return 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer token = new StringTokenizer(br.readLine());

        // Build Graph
        capacity = new int[52][52];
        flow = new int[52][52];

        int n = Integer.parseInt(token.nextToken());
        for(int i=0;i<n;i++){
            token = new StringTokenizer(br.readLine());
            int start = atoi(token.nextToken().charAt(0));
            int end = atoi(token.nextToken().charAt(0));
            int weight = Integer.parseInt(token.nextToken());
            capacity[start][end] += weight;
            capacity[end][start] += weight;
        }

        int totalFlow = 0;
        int source = 0, sink = 25;
        while(true) {
            int[] parent = new int[52];
            Queue<Integer> queue = new PriorityQueue();
            for(int i=0;i<52;i++) parent[i] = -1;
            parent[source] = source;
            queue.add(source);

            while(!queue.isEmpty() && parent[sink] == -1) {
                int here = queue.poll();
                for(int there=0; there<52; there++) {
                    if (capacity[here][there] - flow[here][there] > 0
                        && parent[there] == -1) {
                        queue.add(there);
                        parent[there] = here;
                    }
                }
            }

            // 더이상 증가 경로가 없으면 종료한다.
            if (parent[sink] == -1) break;

            // 증가 경로를 찾았으면 유량을 결정한다.
            int amount = Integer.MAX_VALUE;
            for(int i = sink; i!=source; i=parent[i]) {
                amount = Math.min(capacity[parent[i]][i] - flow[parent[i]][i], amount);
            }

            // 증가 경로를 통해 유량을 보낸다.
            for(int i = sink; i!=source; i=parent[i]) {
                flow[parent[i]][i] += amount;
                flow[i][parent[i]] -= amount;
            }

            totalFlow += amount;
        }

        bw.write(totalFlow+"\n");
        bw.close();
    }
}