백준 17471 게리맨더링

문제:

17471번: 게리맨더링

코드:

/* 1. 마을 번호 1부터 시작! */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int pop[10];
vector<int> adj[10];
bool perm[10];
bool side;
int sz[2], sum[2];
bool vst[10];
int dif;
int ans = 1000;

void DFS(int v) {
	vst[v] = 1;
	for (auto w : adj[v]) {
		if (vst[w] || perm[w] != side)
			continue;
		++sz[side];
		sum[side] += pop[w];
		DFS(w);
	}
}

void DFS_util(bool s) {
	side = s;
	int v;
	for (v = 0; v < N && perm[v] != s; ++v);
	sum[s] = pop[v];
	DFS(v);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int v = 0; v < N; ++v) 
		cin >> pop[v];

	for (int v = 0; v < N; ++v) {
		int vn; cin >> vn;
		while (vn--) {
			int w; cin >> w;
			adj[v].push_back(w - 1);	/* 1 */
		}
	}

	for (int r = 1; r <= N / 2; ++r) {
		fill(perm, perm + N, 0);
		for (int rr = N - 1; rr >= N - r; --rr)
			perm[rr] = 1;
		do {	// nCr
			fill(vst, vst + N, 0);
			sz[0] = sz[1] = 1;

			DFS_util(0);
			DFS_util(1);

			if (sz[0] == N - r && sz[1] == r) {
				dif = abs(sum[0] - sum[1]);
				if (dif < ans)
					ans = dif;
			}
		} while (next_permutation(perm, perm + N));
	}
	if (ans == 1000)	cout << -1;
	else				cout << ans;
	return 0;
}