백준1867 돌멩이 제거

작성일 | In

문제 링크

  • http://icpc.me/1867

문제 출처

  • 2005 November Gold 1번

사용 알고리즘

  • Network Flow
  • Max Flow
  • Bipartite Match

풀이

이 문제와 비슷하게 풀면 됩니다.

(i, j)에 있는 돌멩이를 제거하기 위해서는 i행에 존재하는 돌멩이를 모두 제거하거나, j열에 존재하는 돌멩이를 모두 제거하면 됩니다.

행을 담당하는 정점과 열을 담당하는 정점을 각각 만들어주면 이분 그래프가 만들어지므로 이분 매칭을 돌리면 됩니다.

전체 코드

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
38
#include <bits/stdc++.h>
using namespace std;

int par[1010];
int chk[1010];
vector<int> g[101010];
int bias = 500;

int n, k;

bool dfs(int v){
	chk[v] = 1;
	for(auto i : g[v]){
		if(chk[i]) continue;
		chk[i] = 1;
		if(par[i] == -1 || dfs(par[i])){
			par[i] = v; return 1;
		}
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for(int i=1; i<=k; i++){
		int a, b; cin >> a >> b;
		g[a].push_back(b+bias);
	}

	memset(par, -1, sizeof par);
	int ans = 0;
	for(int i=1; i<=500; i++){
		memset(chk, 0, sizeof chk);
		ans += dfs(i);
	}
	cout << ans;
}