백준14498 학급비 낭비하기

작성일 | In

문제 링크

  • http://icpc.me/14498

문제 출처

  • 2017 선린 봄맞이 대회 L번

사용 알고리즘

  • 이분 매칭

시간복잡도

  • O(nm)

풀이

올해까지 백준에서 진행된 교내대회 중 최고난도 문제이자, 출제자가 만점 방지 문제라고 직접 말한 문제입니다.
사실, 사용되는 알고리즘이 어려운 것이고 해당 알고리즘만 안다면 간단하게 풀 수 있는 문제입니다.

문제를 그래프로 모델링해봅시다.
뽁뽁이 구매를 희망하는 학생들의 그룹을 A라고 하고, 꼭꼭이 구매를 희망하는 학생들의 그룹을 B라고 합시다.
학생들은 특정 꼭꼭이를 구매하지 않기를 바라거나(A), 특정 뽁뽁이를 구매하지 않기를 바랍니다.(B)
의견이 충돌하는 학생끼리 간선으로 이어준다면, 같은 그룹에 있는 학생끼리는 절대 연결되지 않습니다.
여기까지 온다면 이분 매칭 문제인 것을 바로 알 수 있습니다.

전체 코드

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
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

vector<int> g[600];
int arr[600][3];
vector<int> par(600, -1);
bool chk[600];

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

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m, k; cin>>n>>m>>k;

	for(int i=0; i<k; i++){
		cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
	}

	//make graph
	for(int i=0; i<k; i++){
		for(int j=i+1; j<k; j++){
			if((arr[i][0]==arr[j][0] || arr[i][1]==arr[j][1]) && arr[i][2]!=arr[j][2]){
				if(arr[i][2]) g[j].push_back(i);
				else g[i].push_back(j);
			}
		}
	}

	int ans = 0;
	for(int i=0; i<k; i++){
		memset(chk, 0, sizeof(chk));
		if(match(i)) ans++;
	}
	cout << ans;
}