BOJ_2188 축사

2188 축사

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

 

분류

1. 네트워크 유량

2. 애드몬드-카프 알고리즘

3. BFS

4. 이분 매칭

    

TIPS

1. 포드 - 풀거슨 알고리즘을 풀 때, v -> u로 가는 용량이 주어진다면, u -> v로 가는 용량 0의 간선을 만들어 주어야 한다.
2. 코드에서는 capacity[][] 배열을 사용해서 그래프를 나타내준다면, 초기값이 0이기 때문에 1번의 내용을 생각해줄 필요가 없다. 하지만 간선 찾는 시간을 단축시키기 위해 인접리스트로 그래프를 표현했다면, 꼭 인접리스트에 반대로 가는 가상의 간선을 만들어주어야한다. 처음부터 그래프를 배열로 했다면 상관없다.
3. 이분 매칭은 source와 sink가 여러개인 네트워크 유량문제에서 super source와 super sink를 만들어 준다.

 

CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
​
public class BOJ_2188 {
    static StringTokenizer st;
    static final int MAX = 500;
​
    static int N; // 200
    static int M; // 200
    static int[] parent = new int[402];
    static int[][] capacity = new int[402][402];
    static int[][] flow = new int[402][402];
    static ArrayList<Integer>[] graph = new ArrayList[402];
​
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
​
        for (int i = 0; i < N + M + 2; i++) {
            graph[i] = new ArrayList<>();
        }
​
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
​
            for (int j = 0; j < num; j++) {
                int to = N + Integer.parseInt(st.nextToken());
                graph[i].add(to);
                graph[to].add(i);
                capacity[i][to] = MAX;
            }
        }
​
        int s = 0;
        int t = N + M + 1;
​
        for (int i = 1; i < N + 1; i++) {
            graph[s].add(i);
            capacity[s][i] = 1;
        }
​
        for (int i = N + 1; i < t; i++) {
            graph[i].add(t);
            capacity[i][t] = 1;
        }
​
        int total = 0;
​
        while (true) {
            Arrays.fill(parent, -1);
            parent[s] = s;
            Queue<Integer> q = new LinkedList<>();
            q.add(s);
            while (!q.isEmpty()) {
                int current = q.poll();
                if (current == t) break;
​
                for (int next : graph[current]) {
                    if (capacity[current][next] - flow[current][next] > 0 && parent[next] == -1) {
                        q.add(next);
                        parent[next] = current;
                    }
                }
            }// augment
​
            if (parent[t] == -1) break;
​
            for (int i = t; i != s; i = parent[i]) {
                flow[parent[i]][i] += 1;
                flow[i][parent[i]] -= 1;
            }
            total += 1;
​
        }
​
        System.out.println(total);
​
    }
}
​

 

MORE

포드-풀커슨 알고리즘은 이해했지만, 구현하는 과정에서 u->n 유량의 반대 n->u의 간선을 만들어 주어야 한다는 것을 계속 잊어버린다. 구현할 때 좀더 신경을 쓰도록 하자.

이분매칭에서 유량을 설정할때 super source 에서 각 source로 가는 간선은 유량이 되고(축사니까 유량이 1이다). 각 source에서 sink로 가는 모든 간선은 무한대로 표현한다.