[백준 14750] Jerry and Tom

최대 유량 문제

www.acmicpc.net/problem/14750

www.acmicpc.net/problem/2188  www.acmicpc.net/problem/17387

위의 두 문제를 먼저 푸는 것을 권장합니다.

해당 문제들을 풀이할 수 있다고 생각하고 설명하겠습니다.

---

[문제 풀이]

 

n개의 벽에 k마리가 들어갈 수 있는 구멍 h개와 m마리의 쥐가 존재할 때 구멍에 들어갈 수 있는 쥐의 수의 최댓값을 구하는 문제입니다.

 

다른 모든 조건은 생각하지 않고 k마리가 들어갈 수 있는 구멍 h개에 쥐 m마리를 넣을 때의 가능한 최대 마릿수를 생각해봅시다.

 

m마리의 쥐를 h개 구멍에 넣는 최댓값.

최대 유량을 떠올릴 수 있어야 합니다.

 

최대 유량이 떠오르지 않았다면 백준 2188번 축사 배정을 풀어보는 것을 권장합니다.

 

해당 아이디어를 그림으로 그려보자면 아래와 같습니다.

 

파란 테두리: 소스  /  노란 테두리: 쥐  /  갈색 테두리: 구멍  /  빨간 테두리: 싱크

 

시작 정점에서 모든 쥐들로 1만큼의 용량이 존재하고, m마리의 쥐들과 h마리의 구멍 사이에 어떠한 간선이 존재하고, 구멍의 용량은 k여야 하므로 위의 그림과 같습니다.

 

 

결국 쥐들과 구멍 사이의 간선 정보가 필요한 문제입니다.

축사 배정 문제에서는 특정 소가 특정 축사를 희망한다는 정보를 바로 제공했으나 해당 문제는 한 번 꼬았습니다.

쥐와 구멍 사이의 간선에 대한 정보를 직접 구해야 합니다.

 

이때 쥐와 간선에 대한 정보를 얻기 위해 선분 교차 판정을 사용합니다.

쥐와 구멍 사이를 직선으로 이었을 때 사이에 벽이 존재한다면 해당 구멍은 들어갈 수 없는 구멍입니다.

점과 쥐 사이의 직선을 만들고, 모든 모서리에 대해 교차하는지 확인하여서 교차하지 않는다면 해당 점과 쥐를 용량이 1인 간선으로 이어주면 됩니다.

 

구멍 H, 쥐 M

위 그림과 같이 $\overline{HM}$이  $\overline{CD}$,  $\overline{HM}$과 교차하므로 해당 쥐 M과 구멍 H에 대한 간선은 없다고 판단하는 것입니다.

 

구멍 H, 쥐 M

위 그림과 같이 $\overline{HM}$사이에 교차하는 모서리가 없는 경우는 해당 쥐 M과 구멍 H에 대해 용량이 1인 간선을 추가해주면 됩니다.

 

 

그러나 모든 구멍이 모서리 위에 존재하기 때문에 적어도 한 번은 모서리와 교차하게 됩니다.

위 그림을 보아도 $\overline{HM}$과 $\overline{FA}$가 교차했음을 알 수 있습니다.

 

그러므로 어떠한 모서리와도 교차하지 않은 경우에 간선을 추가하는 것이 아닌, 단 한 개의 모서리와 교차한 경우 쥐가 해당 구멍에 들어갈 수 있다고 판정하면 됩니다.

 

하지만 또 하나의 문제가 발생합니다.

대부분의 선분 교차 판정 문제가 그러하듯이 꼭짓점 교차에서 문제가 발생합니다.

 

구멍 H, 쥐 M

위의 경우, $\overline{HM}$은  $\overline{EF}$,  $\overline{FA}$와 교차하지만 M은 H에 들어갈 수 있는 형태입니다.

하지만 위의 경우만 반례가 발생하므로 꼭짓점이 H과 동일한 좌표인 경우 continue하여 교차한 횟수를 세지 않음으로써 문제를 해결할 수 있습니다.

 

이런 방식으로 쥐와 구멍 사이의 간선까지 추가해주고 최대 유량 알고리즘을 동작하면 문제가 해결됩니다.

최대 유량 문제는 그래프를 모델링하는 것이 어려운 문제이므로 최대 유량 알고리즘까지는 설명하지 않겠습니다.

 

해당 풀이는 모든 모서리 n에 대해 모든 쥐와 구멍의 조합 h * m이 교차하는지 확인하므로 $O(nhm)$,

최대 유량 알고리즘인 에드몬드 카프 알고리즘을 사용하는 경우 $O(min(VE^2, Ef))$이고 해당 문제에서는 Ef가 더 작으므로 $O((mh + m + h)f)$,

즉 $O(nhm + (mh + m + h)f)$의 시간 복잡도를 갖습니다.

거창해 보이지만 n의 제한이 1000, h가 50, m이 250, 그리고 f가 m과 같으므로 시간 안에 통과가 가능합니다.

 

---

[소스 코드] / Java

 

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

public class Main {
    private static int N, k, h, m;
    private static Point[] dots, holes, mice;
    private static int[][] c, f;
    private static ArrayList<ArrayList<Integer>> adj;

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

        N = Integer.parseInt(st.nextToken()); k = Integer.parseInt(st.nextToken()); h = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
        dots = new Point[N + 1]; holes = new Point[h]; mice = new Point[m];
        c = new int[h + m + 2][h + m + 2]; f = new int[h + m + 2][h + m + 2];
        adj = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
            dots[i] = new Point(x, y);
        }
        dots[N] = dots[0];

        for (int i = 0; i < h; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
            holes[i] = new Point(x, y);
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
            mice[i] = new Point(x, y);
        }

        for (int i = 0; i < m + h + 2; i++) {
            adj.add(new ArrayList<>());
        }

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

        for (int i = 0; i < h; i++) {
            adj.get(i + m).add(m + h + 1); adj.get(m + h + 1).add(i + m);
            c[i + m][m + h + 1] = k;
        }

        addEdges();
        System.out.println(maxFlow());

        br.close();
    }

    private static void addEdges() {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < h; j++) {
                if (!isCrossed(mice[i], holes[j])) {
                    adj.get(i).add(j + m); adj.get(j + m).add(i);
                    c[i][j + m] = 1;
                }
            }
        }
    }

    private static boolean isCrossed(Point M, Point H) {
        int count = 0;
        for (int i = 0; i < N; i++) {
            Point p1 = dots[i], p2 = dots[i + 1];
            if (H.x == p1.x && H.y == p1.y) continue;

            int S1 = CCW(M, H, p1), S2 = CCW(M, H, p2), S3 = CCW(p1, p2, M), S4 = CCW(p1, p2, H);
            int S12 = S1 * S2, S34 = S3 * S4;

            if (S12 <= 0 && S34 < 0 || S12 < 0 && S34 <= 0) count++;
            else if (S12 == 0 && S34 == 0 && isOneLine(p1, p2, M, H)) count++;

            if (count > 1) return true;
        }

        return false;
    }

    private static boolean isOneLine(Point p1, Point p2, Point p3, Point p4) {
        int A, B, C, D;

        if (p1.x == p2.x) {
            A = Math.min(p1.y, p2.y);
            B = Math.max(p1.y, p2.y);
            C = Math.min(p3.y, p4.y);
            D = Math.max(p3.y, p4.y);
        } else {
            A = Math.min(p1.x, p2.x);
            B = Math.max(p1.x, p2.x);
            C = Math.min(p3.x, p4.x);
            D = Math.max(p3.x, p4.x);
        }

        return A <= D && C <= B;
    }

    private static int CCW(Point p1, Point p2, Point p3) {
        long S = (long) p1.x * p2.y + (long) p2.x * p3.y + (long) p3.x * p1.y;
        S -= (long) p1.y * p2.x + (long) p2.y * p3.x + (long) p3.y * p1.x;
        return S == 0 ? 0 : S > 0 ? 1 : -1;
    }

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

        while (true) {
            int minFlow = 15000;
            int[] prev = new int[m + h + 2];
            Queue<Integer> q = new LinkedList<>();

            Arrays.fill(prev, -1);
            q.add(m + h);
            prev[m + h] = -2;

            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[m + h + 1] == -1) break;

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

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

            result += minFlow;
        }

        if (result == m) return "Possible";
        else return "Impossible";
    }

    private static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}