지민이는 파티에 가서 이야기 하는것을 좋아한다.
지민이는 되도록 파티에가서 과장된 이야기를 하려고하는데 몇명의 사람들이 진실을 알고있다.
진실을 아는 사람이 있는 파티에는 과장된 이야기를 하면안되고 진실을 알지 못하더라도
어떤 파티에서는 과장된이야기를, 어떤 파티에서는 과장되지 않은이야기를 들으면 안된다.
지민이가 과장된 이야기를 할 수 있는 파티의 최댓값을 구하는 문제이다.
문제를 보고 이상하게 유량문제로 접근했다.
모델링을 계속 시도해보았지만 적절치 않아서 플로이드 와샬로 진실을 아는 사람이 있는 파티와
연관된 파티들을 인접리스트로 연결시켜주는 방식을 이용해서 최대유량을 구했다.
사실 최대유량을 구할 필요도 없이 플로이드 와샬로 위에서 말한방식처럼 연결시킨 후
bfs로 탐색시켜주면 끝난다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 987654321
int N, M;
int num;
bool knowtrue[51];
bool chk[51][51];
bool chkadj[51][51];
vector<int> adj[111];
bool visit[111];
int main() {
scanf("%d%d", &N, &M);
scanf("%d", &num);
for (int n = 0, t;n < num;n++) scanf("%d", &t), knowtrue[t - 1] = true;
for (int m = 0;m < M;m++) {
scanf("%d", &num);
for (int n = 0, t;n < num;n++) scanf("%d", &t), chk[m][t - 1] = true;
}
for (int m = 0;m < M;m++) {
for (int k = 0;k < M;k++) {
for (int n = 0;n < N;n++) {
if (chk[m][n] && chk[k][n]) {
chkadj[m][k] = true;
chkadj[k][m] = true;
break;
}
}
}
}
for (int k = 0;k < M;k++) {
for (int n = 0;n < M;n++) {
for (int m = 0;m < M;m++) {
if (!chkadj[n][m] && chkadj[n][k] && chkadj[k][m]) chkadj[n][m] = true;
}
}
}
for (int n = 0;n < M;n++) {
for (int m = 0;m < M;m++) {
if (chkadj[n][m]) {
adj[n].push_back(m + M);
}
}
}
queue<int> q;
for (int m = 0;m < M;m++) {
bool flag = false;
for (int n = 0;n < N;n++) if (knowtrue[n] && chk[m][n]) { flag = true; break; }
if (flag) q.push(m), visit[m] = true;
}
while (!q.empty()) {
int here = q.front();
q.pop();
for (int &next : adj[here]) {
if (!visit[next]) {
visit[next] = true;
q.push(next);
}
}
}
int ans = 0;
for (int m = 0;m < M;m++) {
if (!visit[m + M]) ans++;
}
printf("%d\n", ans);
return 0;
}
| cs |
저는 그래서 그래프를 먼저 그려보긴 합니다.
답글삭제먼저 그려보는 습관을 가져야겠어요 ㅋㅋ
삭제