풀이
이분그래프에서의 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이