백준1587 이분 매칭

작성일 | In

문제 링크

  • http://icpc.me/1587

사용 알고리즘

  • DP
  • General Matching

시간복잡도

  • $O(\vert V \vert)$

풀이

$D(i, j) := $ 왼쪽 $1\cdots i$번 정점, 오른쪽 $1\cdots j$번 정점만 고려했을 때의 최대 매칭이라고 정의합시다. 상태 전이는 쉽게 구할 수 있습니다.

  • $i-1, i$ 매칭 : $D(i, j) \leftarrow D(i-2, j) + 1$
  • $j-1, j$ 매칭 : $D(i, j) \leftarrow D(i, j-2) + 1$
  • $i-1, i, j-1, j$ 매칭 : $D(i, j) \leftarrow D(i-2, j-2) + 2$
  • $i, j$ 매칭 : $D(i, j) \leftarrow D(i-1, j-1) + 1$

혹은 그래프의 크기가 작다는 점을 이용해 Blossom Algorithm을 이용해서 General Matching을 구해도 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int N, M, K, G[1010][1010], D[1010][1010], R;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> K;
    for(int i=1,s,e; i<=K; i++) cin >> s >> e, G[s][e] = 1;
    for(int i=0; i<=N; i++){
        for(int j=0; j<=M; j++){
            if(i >= 2) D[i][j] = max(D[i][j], D[i-2][j] + 1);
            if(j >= 2) D[i][j] = max(D[i][j], D[i][j-2] + 1);
            if(i >= 2 && j >= 2) D[i][j] = max(D[i][j], D[i-2][j-2] + 2);
            if(G[i][j]) D[i][j] = max(D[i][j], D[i-1][j-1] + 1);
            R = max(R, D[i][j]);
        }
    }
    cout << R;
}