BOJ 2188: 축사 배정

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (27/187)
  • 감이 잘 오지 않는 이분매칭. 일단 자손님 블로그 코드를 보면서 풀었다.
  • 기본 흐름은 아래와 같다.

    현재 노드를 매칭할 수 없을 때, 먼저 매칭한 노드를 다른 곳으로 옮긴 뒤 매칭한다. 매 노드 매칭에서, 옮길 노드를 고를때 DFS를 한다.

  • 사실 Greedy 알고리즘이 사용되는데,
    • 현재 선택을 위해서, 단순하게 최대한 매칭해보는 식으로 진행하면 최적해가 나오기 때문이다.
    • 증명을 위해서는 Network Flow 이론을 공부해야 할 것 같다.

Network Flow 그래프의 3가지 조건

  1. Capacity Law: Edge에 부여된 Flow는 Capacity 이상일 수 없다.
  2. Conservation Law: Vertice로 들어오는 Flow들의 합은 0이다.
  3. Skew Symmetry Law: 두 vertice u,v에 대해서 f(u,v) = -f(v,u) 이다.

Implicit Sumation Notation

1
|F| = Sigma for every v in V f(s, v) = f(s,V)

이제 집합에 대해서도 Flow를 쓸 수 있음

  1. f(X,X) = 0
  2. f(X,Y) = -f(Y,X)
  3. f(X U Y, Z) = f(X,Z) + f(Y,Z) if X intersect Y = Null

이제 저거를 이용해서 현재 흐르는 Flow가 아래임 소스로부터 나머지 V로 가는 flow임을 정의할 수 있음. 그리고 이게 sink로 향하는 flow인것도 증명 가능.

1
|F| = f(s, V) = f(V, t)

이제 Cut이라는게 나오는데, Sink를 포함한 Vertice랑 Source를 포함한 Vertice를 S,T 집합으로 나눈거임. 근데 Cut에 흐르는 Flow가 현재 흐르는 flow와 같다는게 성립. 이걸 이용하면 min-cap-cut이 max-flow를 결정한다는 것을 이끌어 낼 수 있음

1
2
C(S,T) = capacity of cut
f(S,T) = flow of cut = current flow = |F|

이제 Residual Network에서 BFS를 하면 된다. 아래부터는 구사과의 블로그에서 발췌

  1. 그래프에서 source에서 sink로 흐를 수 있는 최대 유량, Maximum Flow를 찾는 문제이다.
  2. 기본적인 알고리즘은, 증가 경로를 “어떻게든” 찾은 후 그 쪽으로 flow를 보내주는 방식으로 해결한다. 탐욕법의 일종이다. 이를 Ford-Fulkerson Algorithm이라고 한다. Ford-Fulkerson Algorithm은 증가 경로를 구체적으로 어떻게 찾는지 명시하지 않았다. 지수적인 방법으로 찾아도 포드 풀커슨이고 고로 이걸 Ford-Fulkerson Method로 불러야 한다는 의견도 존재한다. 다행이 우리는 BFS나 DFS를 아니까 둘 중 하나를 쓰면 된다.
  3. DFS든, BFS든 기본적으로 시간 복잡도는 O(f * E) 이다. f는 유량의 총 크기로 만약 크기가 확실치 않다면 다항시간에 풀 수 없는 것이나 마찬가지다.
  4. 하지만 BFS를 사용했을때는 증가 경로를 VE번 이상 찾지 않는다는 것이 증명되었다. 증명 따라서 Maximum Flow 문제는 무조건 BFS를 사용해야 하며 시간 복잡도는 O(VE^2)이다. BFS를 쓰는 Ford-Fulkerson Algorithm을 Edmonds-Karp Algorithm이라고 부른다. 출처: https://koosaga.com/18 [구사과]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

int N, M, k, tmp, ans;
vector<int> wants[201];
vector<int> selected;
vector<int> visit;

bool bimatch(int n) {
  if(visit[n]) return false;
  visit[n] = 1;
  for(int w : wants[n]) {
    if(!selected[w] || bimatch(selected[w])) {
      selected[w] = n;
      return true;
    }
  }
  return false;
}

int main() {
  cin >> N >> M;
  for(int i = 1; i <= N; i++) {
    cin >> k;
    for(int j = 0; j < k; j++) {
      cin >> tmp;
      wants[i].push_back(tmp);
    }
  }

  selected = vector<int>(M+1, 0);
  for(int i = 1; i <= N; i++) {
    visit = vector<int>(N+1, 0);
    if(bimatch(i)) ans++;
  }
  cout << ans;
}