3683 고양이와 개 https://www.acmicpc.net/problem/3683
두 문제 동일한 문제나 다름없다.
고양이와 개 문제에 대해서 아주 좋은 설명이 있으니 이 설명으로 마무리한다.
고양이를 좋아하는 그룹 내의 사람들끼리는 모순(둘 중 한 명의 의견은 무시당해야만 하는 경우)이 생길 일이 없고,
개를 좋아하는 그룹 내의 사람들끼리는 모순이 생길 일이 없습니다.
따라서 고양이를 좋아하는 그룹/개를 좋아하는 그룹으로 나눈 뒤 서로 양립할 수 없는 사람들 간에만 간선을 이어서 이분 그래프를 만듭니다.
이때 이 이분 그래프에서 간선, 즉 매칭은 의견의 충돌 1회를 의미합니다.
의견의 충돌을 모두 없애기 위해서는 어떤 매칭도 남지 않게 되면 되겠네요.
어떤 매칭도 남지 않는다는 것은 해당 이분 그래프로 네트워크를 구성했을 때 유량이 더이상 흐를 수 없다는 것과 동치가 됩니다.
유량이 흐를 수 없도록 해야 한다? 네. 네트워크에 대한 컷을 구하는 문제로 바뀌게 됩니다.
컷에 속한 간선 하나당 해당 간선 양 끝점의 두 사람 중 한 사람의 의견을 무시하는 것과 같다고 생각하시면 됩니다.
우리는 무시당하는 인원을 최소화하고 싶네요. 그럼 컷 중에서도 민컷을 구하면 됩니다. 민컷 = 최대유량 = 최대 매칭이므로,
총 시청자 수에서 해당 이분 그래프에서의 최대 매칭을 빼 주면 답이 됩니다.
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int c, d, V;
int C[555][555], f[555][555];
string x, y;
int maximum_flow(const int S, const int E, const vector<vector<int>> &adj) {
int ret = 0;
while (1) {
queue<int> q;
vector<int> par(V + 2, -1);
q.push(S);
while (!q.empty() && par[E] == -1) {
int here = q.front();
q.pop();
for (int next : adj[here]) {
if (C[here][next] - f[here][next] > 0 && par[next] == -1) {
q.push(next);
par[next] = here;
}
}
}
if (par[E] == -1) break;
for (int i = E;i != S;i = par[i])
f[par[i]][i]++, f[i][par[i]]--;
ret++;
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
memset(C, 0, sizeof C);
memset(f, 0, sizeof f);
cin >> c >> d >> V;
const int src = 0, sink = V + 1;
vector<pair<string, string>> input(V + 1);
vector<vector<int>> adj(V + 2, vector<int>());
for (int v = 1;v <= V;v++) {
cin >> x >> y;
input[v] = { x,y };
}
for (int n = 1;n <= V;n++) {
if (input[n].first[0] == 'C') {
for (int m = 1;m <= V;m++) {
if (input[n].first == input[m].second || input[n].second == input[m].first) {
adj[n].push_back(m);
adj[m].push_back(n);
C[n][m] = 1;
}
}
adj[src].push_back(n);
adj[n].push_back(src);
C[src][n] = 1;
}
else {
adj[n].push_back(sink);
adj[sink].push_back(n);
C[n][sink] = 1;
}
}
int ans = V - maximum_flow(src, sink, adj);
cout << ans << "\n";
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기