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

2021/02/13 동계 모각코 6회차

오늘 공부하고자 했던 정점 분할에 대한 이해와 문제 풀이를 마쳤습니다.

---

[정점 분할] www.acmicpc.net/problem/2316

최대 유량에서 정점의 중복마저 제거하는 문제입니다.

 

정점 분할은 하나의 알고리즘이라기보다는 최대 유량 문제에서 그래프를 구성하는 하나의 스킬입니다.

일반적인 최대 유량 문제에서는 간선의 용량만 신경 써줘도 문제가 해결이 가능했으나 위 문제처럼 정점의 중복을 예방하기 위해서는 정점 분할이 필요합니다.

 

우선 최대 유량 문제에서는 간선을 선택하는 순서에 상관없이 최적의 선택을 하기 위해 음의 유량이라는 개념을 도입하였습니다.

단순하게 최대 유량을 흘릴 때에는 간선을 선택하는 순서에 따라 최적이 달라지는 문제가 발생합니다.

그러나 그런 상황을 방지하도록 이전의 선택을 철회할 수 있게 음의 유량이라는 비교적 간단한 개념을 도입한 것입니다.

 

하지만 여기서 정점의 중복을 막는다면 조금 문제가 생기게 됩니다.

이전까지 간선에 흐른 유량을 음의 유량으로 철회할 수 있게 했는데, 단순히 정점의 중복을 막기 위해 bool배열을 하나 만든다면 정점의 중복에 대한 철회는 꽤나 까다롭게 됩니다.

 

그래서 등장한 개념이 정점 분할입니다.

정점 분할의 개념은 단순히 하나의 정점 V를 두 정점 V_in과 V_out으로 나눠 원래 유량에서 들어오는 역할은 V_in이, 내보내는 역할은 V_out이 하게 되고 V_in과 V_out사이의 용량을 1로 설정한다면 이미 중복되는 정점에 대해서도 최대 유량 알고리즘 실행 과정 중에 자연히 철회가 가능하게 됩니다.

 

 

[후기]

 

사실 해당 문제가 아닌 이번 목표는 삼분 탐색이었으나, 여러 악재로 인해 지난 회차에 배운 내용의 연장인 정점 분할을 다루게 되었습니다.

 

원래 의도한 바는 아니었으나 좋은 문제를 접한 것 같고, 최대 유량은 정말 그래프를 구성하는 과정이 중요한 것 같습니다.

초기 그래프 설정을 잘 짜고 최대 유량 알고리즘을 돌리면 문제가 해결이 되는 경우가 대부분인 것 같습니다.

 

 

[소스 코드]

 

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

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

    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()), P = Integer.parseInt(st.nextToken());
        adj = new ArrayList<>();
        f = new int[2 * N + 1][2 * N + 1]; c = new int[2 * N + 1][2 * N + 1];

        for (int i = 0; i < 2 * N + 1; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 1; i < N + 1; i++) {
            adj.get(i).add(i + N); adj.get(i + N).add(i); c[i][i + N] = 1;
        }

        while (P-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int iu = Integer.parseInt(st.nextToken()), iv = Integer.parseInt(st.nextToken());
            int ou = iu + N, ov = iv + N;

            adj.get(ou).add(iv); adj.get(iv).add(ou); c[ou][iv]++;
            adj.get(ov).add(iu); adj.get(iu).add(ov); c[ov][iu]++;
        }

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

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

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

            Arrays.fill(prev, -1);
            q.add(1 + N);
            prev[1 + N] = 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;

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

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

            result += minFlow;
        }

        return result;
    }
}