[백준] 13161 분단의 슬픔 + 디닉 알고리즘

문제

UCPC에는 N명의 사람이 있다. 먼 옛날 쇼킹핫치킨에 대한 논쟁에서 시작된 이념의 대립으로 UCPC에는 kriii를 따르는 쇼킹핫진보 진영 A와, august14를 따르는 쇼킹핫보수 진영 B의 두 진영이 존재한다. 모든 사람은 둘 중 한 진영에 소속되어 있으며, 두 진영에 동시에 들어가는 것은 불가능하다.

i번 사람과 j번 사람에 대해 서로 다른 진영에 들어가게 될 경우 슬픈 정도 w[i, j]가 주어진다. 일부 사람들은 쇼킹핫에 관한 자신의 철학이 강해 무조건 A진영에 들어가는 사람도 있고, 무조건 B진영에 들어가는 사람도 있다. 물론 치킨은 무엇이든 옳으므로 두 진영 어디에 가든 상관없는 사람도 있다.

N명의 사람들이 적절히 두 진영에 나누어 들어갈 때, 슬픔 정도의 합이 최소가 되게 하라.

입력

첫 번째 줄에는 UCPC 구성원의 수 N(1 ≤ N ≤ 500)이 주어진다. 두 번째 줄에는 N개의 정수가 주어지는데, i번째 수가 1이면 i번 사람은 무조건 A진영에 들어가야 함을, 2라면 무조건 B진영에 들어가야 함을, 0이면 어느 진영에 들어가든지 상관 없다는 것을 의미한다.

세 번째 줄부터 N개의 줄에 걸쳐 i번 사람과 j번 사람이 다른 진영에 들어갈 때의 슬픔 정도 w[i, j]가 주어진다. (i+2)번째 줄에 j번째 수는 w[i, j]를 의미한다. 주어지는 입력은 항상 w[i, j]=w[j, i]를 만족하고, w[i, i]=0이다. w[i, j]는 1,000보다 크지 않은 음이 아닌 정수이다.

출력

첫 줄에 N명의 사람이 A, B 두 진영에 적절히 들어가 슬픈 정도의 합이 최소가 될 때의 슬픔 정도의 합을 출력한다. 두 번째 줄에는 슬픈 정도의 합이 최소가 될 때 A진영에 들어가는 사람들의 번호를 공백으로 구분하여 출력하고, 세 번째 줄에는 슬픈 정도의 합이 최소가 될 때 B진영에 들어가는 사람들의 번호를 공백으로 구분하여 출력한다. 만약 한 진영에 사람이 한 명도 들어가지 않은 경우 빈 줄을 출력한다. 가능한 경우가 여러 가지인 경우 그중 아무거나 하나 출력한다

 

일반적인 플로우 최대유량을 구하는 문제는 몇가지 알고리즘으로는

포드 풀커슨 , 에드몬즈 카프 알고리즘이 있습니다.

 

포드 풀커슨과 에드먼드 카프알고리즘은 모두

반복하여 증가경로를 찾고,

증가경로를 따라 유량을 흘리는행동을 반복합니다.

포드 풀커슨은 DFS를 이용해 증가경로를찾고, 에드몬드 카프알고리즘은 BFS를 이용해 증가경로를 찾습니다.

 

이보다 더 빠른 알고리즘이 있습니다.

디닉 알고리즘입니다.

 

디닉 알고리즘은

반복하여 증가경로를 찾기 전에, 레벨그래프를 먼저 만들고,

증가경로를 찾아 차단유량을 찾아 더합니다.

 

 소스는 레벨이 0이고, 한번 간선을따라 움직일 수 있는 정점의 레벨을 1씩 늘립니다.

레벨그래프는 BFS를 이용해 만듭니다.

그려진 레벨그래프를 기준으로, DFS로 차단유량을 하나씩 흘립니다.

이때는 레벨이 1 높은 정점으로만 흘려야합니다.

work 배열을 사용하는데, 이미 한번 살펴본 정점은 또다시 살펴볼 필요가 없기 때문입니다.

	#include<bits/stdc++.h>
	#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
	#define mset(v) memset(v,0,sizeof(v));
	#define rep(i,a) for(int i=0;i<a;++i)
	#define REP(i,a) for(int i=1;i<=a;++i)

	using namespace std;

	typedef long long ll;
	typedef pair<int, int> pi;
	typedef tuple<int, int, int>ti;
	typedef vector<int> vi;
	typedef vector<vector<int>> vvi;
	int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };

	using namespace std;
	int N, x, level[503], c[503][503], f[503][503], INF = 987654321, work[503], v[503];
	int S = 501, E = 502;
	vi adj[503];
	bool bfs() {
		fill(level, level + 503, -1);
		level[S] = 0;
		queue<int>q;
		q.push(S);
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			for (auto nxt : adj[cur]) {
				if (level[nxt] == -1 && c[cur][nxt]-f[cur][nxt]>0) {
					level[nxt] = level[cur] + 1;
					q.push(nxt);
				}
			}
		}
		return level[E] != -1;
	}
	int dfs(int cur, int to, int flow) {
		if (cur == to)return flow;

		for (int& i = work[cur]; i < adj[cur].size(); i++) {
			int nxt = adj[cur][i];
			if (level[cur] + 1 == level[nxt] && c[cur][nxt] - f[cur][nxt] > 0) {
				int fl = dfs(nxt, to, min(flow, c[cur][nxt] - f[cur][nxt]));
				if (fl>0) {
					f[cur][nxt] += fl;
					f[nxt][cur] -= fl;
					return fl;
				}
			}
		}
		return 0;
	}
	int main() {
		FAST;
		cin >> N;
		REP(i, N) {
			cin >> x;
			if (x == 1) {
			
				c[S][i] = INF;
				adj[S].push_back(i);
				adj[i].push_back(S);
			}
			else if (x == 2) {
		
				c[i][E] = INF;
				adj[i].push_back(E);
				adj[E].push_back(i);
			}
		}
		REP(i, N) {
			REP(j, N) {
				cin >> c[i][j];
				if (i != j) {
					adj[i].push_back(j);
				
				}
			}
		}
		int ans = 0;
		while (bfs()) {
			mset(work);
			while (1) {
				int flow = dfs(S, E, INF);
				if (!flow)break;
				ans += flow;
			}
		}
		cout << ans << "\n";
		v[S] = 1;
		queue<int>q;
		q.push(S);
		while (!q.empty()) {
			auto cur = q.front();
			q.pop();
			for (auto nxt : adj[cur]) {
				if (!v[nxt] && c[cur][nxt] - f[cur][nxt] > 0) {
					v[nxt] = 1;
					q.push(nxt);
				}
			}
		}
		REP(i, N) {
			if (v[i])cout << i << " ";
		}
		cout << "\n";
		REP(i, N) {
			if (!v[i])cout << i << " ";
		}
		cout << "\n";
	}