백준9169 나는 9999번 문제를 풀 수 있다

작성일 | In

문제 링크

  • http://icpc.me/9169

사용 알고리즘

  • Network Flow
  • Max Flow
  • Min Cut

풀이

풀 수 없는 사람은 source와, 풀 수 있는 사람은 sink와 연결해줍시다. 그리고 친구 관계도 간선으로 연결해줍시다.
Min Cut 문제가 됩니다.

Max Flow와 Min Cut은 동치이므로 그래프를 잘 그려준 다음에 Max 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
#include <bits/stdc++.h>
using namespace std;

int c[333][333];
int f[333][333];
vector<int> g[333];
int lv[333];
int work[333];

const int s = 301, t = 302;
int n, m;
int arr[333];
int aa, bb;

bool bfs(){
	memset(lv, -1, sizeof lv); lv[s] = 0;
	queue<int> q; q.push(s);
	while(q.size()){
		int now = q.front(); q.pop();
		for(auto nxt : g[now]){
			if(lv[nxt] == -1 && c[now][nxt] - f[now][nxt] > 0){
				q.push(nxt); lv[nxt] = lv[now] + 1;
			}
		}
	}
	return lv[t] != -1;
}

int dfs(int now, int tot){
	if(now == t) return tot;
	for(int &i=work[now]; i<g[now].size(); i++){
		int nxt = g[now][i];
		if(lv[nxt] == lv[now] + 1 && c[now][nxt] - f[now][nxt] > 0){
			int fl = dfs(nxt, min(tot, c[now][nxt] - f[now][nxt]));
			if(fl > 0){
				f[now][nxt] += fl;
				f[nxt][now] -= fl;
				return fl;
			}
		}
	}
	return 0;
}

int run(){
	int ret = 0;
	while(bfs()){
		memset(work, 0, sizeof work);
		while(1){
			int fl = dfs(s, 1e9);
			if(fl <= 0) break;
			ret += fl;
		}
	}
	return ret;
}

void init(){
	memset(c, 0, sizeof c);
	memset(f, 0, sizeof f);
	for(int i=0; i<333; i++) g[i].clear();
	aa = bb = 0;
}

void addEdge(int s, int e, int x = 1){
	g[s].push_back(e); c[s][e] += x;
	g[e].push_back(s);
}

void solve(){
	init();
	for(int i=1; i<=n; i++){
		int x; cin >> x; arr[i] = x;
		if(x == 0) addEdge(s, i, 1), aa++;
		else addEdge(i, t, 1), bb++;
	}
	for(int i=1; i<=m; i++){
		int a, b; cin >> a >> b;
		if(arr[a] && !arr[b]){
			addEdge(b, a, 1);
		}else if(!arr[a] && arr[b]){
			addEdge(a, b, 1);
		}else{
			addEdge(a, b, 1); addEdge(b, a, 1);
		}
	}
	cout << run() << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	while(1){
		cin >> n >> m;
		if(n == 0 && m == 0) break;
		solve();
	}
}