[붕어빵 꼬리먼저 팀] 5회차 - 학습 마무리

2021/01/28 동계 모각코 5회차

오늘 공부하고자 했던 최대 유량에 대한 이해와 문제 풀이를 마쳤습니다.

---

[최대 유량] www.acmicpc.net/problem/17412

최대 유량을 이용하여 두 도시를 얼마나 많이 왕복할 수 있는지를 구하는 문제입니다.

 

우선 해당 문제에서는 정석적인 최대 유량 문제라기보다, 간선이 추가됨에 따라 용량이 1씩 늘어나는 방식으로 생각합니다.

1번 도시에서 2번 도시까지 흘릴 수 있는 유량의 최대를 구한다면 자연스럽게 1번 도시와 2번 도시를 왕복할 수 있는 횟수를 구할 수 있게 됩니다.

 

간선이 중복될 수 있으므로 용량을 계속 더해줄 수 있도록 합니다.

N의 값이 작으므로 2차원 배열을 사용하였습니다.

 

사용 가능한 알고리즘 중 Edmonds-Karp 알고리즘을 사용하였습니다.

해당 문제에서는 용량의 크기가 1씩 늘어나 최대 용량이 적어서 Ford-Fulkerson알고리즘을 사용하여도 무방하나, 연습을 위해 Edmonds-Karp 알고리즘을 사용하였습니다.

 

 

[소스 코드] / Java

 

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

public class Main {
    private static ArrayList<HashSet<Integer>> adj;
    private static int[][] c, f;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());

        adj = new ArrayList<>();
        c = new int[N + 1][N + 1]; f = new int[N + 1][N + 1];

        for (int i = 0; i < N + 1; i++) {
            adj.add(new HashSet<Integer>());
        }

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
            c[u][v]++;
            adj.get(u).add(v); adj.get(v).add(u);
        }

        System.out.println(maxFlow(N));
        br.close();
    }

    private static int maxFlow(int N) {
        final int INF = 10000;
        int result = 0;

        while (true) {
            Queue<Integer> q = new LinkedList<>();
            int[] prev = new int[N + 1];

            Arrays.fill(prev, -1);
            q.add(1);
            prev[1] = 0;

            while (!q.isEmpty()) {
                int cur = q.remove();

                for (int next : adj.get(cur)) {
                    if (c[cur][next] - f[cur][next] > 0 && prev[next] == -1) {
                        q.add(next);
                        prev[next] = cur;
                    }
                }
            }

            if (prev[2] == -1) break;

            int minFlow = INF;
            for (int i = 2; i != 1; i = prev[i]) {
                minFlow = Math.min(minFlow, c[prev[i]][i] - f[prev[i]][i]);
            }

            for (int i = 2; i != 1; i = prev[i]) {
                f[prev[i]][i] += minFlow;
                f[i][prev[i]] -= minFlow;
            }

            result += minFlow;
        }

        return result;
    }
}