백준13161 분단의 슬픔

작성일 | In

문제 링크

  • http://icpc.me/13161

문제 출처

  • 2016 UCPC C번

사용 알고리즘

  • Network Flow
  • Max Flow
  • Min Cut
  • Dinic

풀이

무조건 A진영에 들어가야 하는 사람은 source와, 무조건 B진영에 들어가야 하는 사람을 sink와 연결해줍시다.
각 사람들도 간선으로 이어줄건데, 입력으로 주어지는 인접 행렬로 가중치를 정할 것입니다.
이렇게 놓고 보니 Min Cut 문제가 되었네요!

그래프가 크기때문에 디닉 알고리즘을 써야 합니다.

전체 코드

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
101
#include <bits/stdc++.h>
using namespace std;

int c[555][555];
int f[555][555];
vector<int> g[555];
int lv[555];
int work[555];
int chk[555];
int n;
int s = 501, t = 502;

bool bfs(){
	memset(lv, -1, sizeof lv);
	queue<int> q; q.push(s);
	lv[s] = 0;
	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){
				lv[nxt] = lv[now] + 1;
				q.push(nxt);
			}
		}
	}
	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;
}

void decom(){
	queue<int> q; q.push(s);
	chk[s] = 1;
	while(q.size()){
		int now = q.front(); q.pop();
		for(auto nxt : g[now]){
			if(!chk[nxt] && c[now][nxt] - f[now][nxt] > 0){
				chk[nxt] = 1;
				q.push(nxt);
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++){
		int x; cin >> x;
		if(x == 1){
			c[s][i] = 1e9+7;
			g[s].push_back(i);
			g[i].push_back(s);
		}
		if(x == 2){
			c[i][t] = 1e9+7;
			g[i].push_back(t);
			g[t].push_back(i);
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin >> c[i][j];
			if(i != j) g[i].push_back(j);
		}
	}

	int ans = 0;
	while(bfs()){
		memset(work, 0, sizeof work);
		while(1){
			int fl = dfs(s, 1e9+7);
			if(!fl) break;
			ans += fl;
		}
	}
	cout << ans << "\n";

	decom();
	vector<int> a, b;
	for(int i=1; i<=n; i++){
		if(chk[i]) a.push_back(i);
		else b.push_back(i);
	}
	for(auto i : a) cout << i << " "; cout << "\n";
	for(auto i : b) cout << i << " "; cout << "\n";
}