문제:icpc.me/9169
풀 수있다고 생각한 사람과 풀 수 없다고 생각한 사람의 생각이 주어지고 사람들의 친구 관계가 주어지는데 이 때 생각을 바꾸거나 친구사이에 투표한 결과가 서로 다른 관계의 수의 합의 최솟값을 구하는 문제이다.
우리는 풀 수 있다고 생각한 사람을 소스에 연결하고 풀 수 없다고 생각한 사람을 싱크에 연결 한 뒤 서로 다른 경우에 간선을 한 방향으로 같은 경우에 양방향으로 연결해줌으로서 그래프를 모델링 해준 뒤 cut의 개수를 구하면 어긋나는(생각이 다른) 경우의 개수이므로 min cut을 구해주면 된다.
mincut은 Maxflow-Mincut Theorem에 의하여 maximum flow를 구해줌으로서 해결 된다.
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cstring> #define S 302 #define E 303 #define INF 987654321 using namespace std; int n, m; class Dinic { public: int a[310]; struct Edge { int v, cap, rev; Edge(int v,int cap,int rev) : v(v), cap(cap), rev(rev) {} }; vector<vector<Edge>> vt; void addEdge(int s, int e, int c) { vt[s].emplace_back(e, c, (int)(vt[e].size())); vt[e].emplace_back(s, 0, (int)(vt[s].size() - 1)); } int level[310], work[310]; bool bfs() { memset(level, -1, sizeof(level)); queue<int> qu; qu.push(S); level[S] = 0; while (qu.size()) { int here = qu.front(); qu.pop(); for (auto i : vt[here]) { int there = i.v; int cap = i.cap; if (level[there] == -1 && cap > 0) { level[there] = level[here] + 1; qu.push(there); } } } return level[E] != -1; } int dfs(int here, int crtcap) { if (here == E)return crtcap; for (int &i = work[here]; i < vt[here].size(); i++) { int there = vt[here][i].v; int cap = vt[here][i].cap; if (level[here] + 1 == level[there] && cap>0) { int c = dfs(there, min(cap, crtcap)); if (c > 0) { vt[here][i].cap -= c; vt[there][vt[here][i].rev].cap += c; return c; } } } return 0; } int calmaxflow() { int ret = 0; while (bfs()) { memset(work, 0, sizeof(work)); while (1) { int flow = dfs(S, INF); if (!flow)break; ret += flow; } } return ret; } }; int main() { while (scanf("%d%d", &n, &m) != EOF) { if (!n&&!m)break; Dinic d; d.vt.resize(310); for (int i = 1; i <= n; i++) { scanf("%d", &d.a[i]); if (d.a[i]) d.addEdge(S, i, 1); else d.addEdge(i, E, 1); } for (int i = 0; i < m; i++) { int x, y; scanf("%d%d", &x, &y); if (d.a[x] && !d.a[y]) d.addEdge(x, y, 1); else if (!d.a[x] && d.a[y]) d.addEdge(y, x, 1); else { d.addEdge(x, y, 1); d.addEdge(y, x, 1); } } printf("%d\n", d.calmaxflow()); } return 0; } | cs |
'알고리즘 관련 > BOJ' 카테고리의 다른 글
BOJ)2787 흔한 수열 문제 (0) | 2017.02.20 |
---|---|
BOJ)2191 들쥐의 탈출 (0) | 2017.02.20 |
BOJ)1017 소수 쌍 (0) | 2017.02.20 |
BOJ)13560 Football (0) | 2017.02.20 |
BOJ)12019 동아리방 청소! (0) | 2017.02.17 |