3683 : 고양이와 개

풀이

이분그래프에서의 Maximum Independent Set(최대 독립 집합)을 구하는 문제이다.

size(maximum independent set) + size(maximum matching) = size(vertices) 이거를 기억하자.

문제를 그래프화 시켜보자. 시청자를 노드, 의견 충돌을 엣지라고 두자.

시청자들은 cat을 남기고 dog를 떨어트리거나, dog를 남기고 cat을 떨어트리는 집단으로 나눌 수 있다. 그렇게 나눠서 엣지를 연결하면 이분그래프가 된다!

그런데 maximum independent set을 구하긴 힘드니까 위의 식을 정리해서, size(vertices) - size(maximum matching)를 구하자!

결국 이분매칭 문제가 되었다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> A[501];
string v1[501], v2[501];
int vst[501];
bool chk[501];

void clean() {
	for (int i = 0; i < 501; ++i) {
		A[i].clear();
		v1[i].clear();
		v2[i].clear();
		vst[i] = -1;
	}
}

int matching(int a) {
	for (auto b : A[a]) {
		if (chk[b]) continue;
		chk[b] = true;
		if (vst[b] == -1 || matching(vst[b])) {
			vst[b] = a;
			return true;
		}
	}
	return false;
}

int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--) {
		clean();
		int c, d, v;
		scanf("%d %d %d", &c, &d, &v);
		for (int i = 0; i < v; ++i)
			cin >> v1[i] >> v2[i];

		for (int i = 0; i < v - 1; ++i) {
			for (int j = i + 1; j < v; ++j) {
				if (v1[i].compare(v2[j]) == 0 || v1[j].compare(v2[i]) == 0) {
					if (v1[i][0] == 'C') A[i].push_back(j);
					else A[j].push_back(i);
				}
			}
		}

		int sum = 0;
		for (int i = 0; i < v; ++i) {
			memset(chk, 0, sizeof(chk));
			if (matching(i)) ++sum;
		}
		printf("%d\n", v - sum);
	}

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-03-06 15:24

Read more posts by this author