BOJ 2453 부서 배치

문제 링크입니다.

문제 요약

$M$개의 조건: x, y가 같은/다른 팀이어야 함을 만족하도록 $N$명의 사람을 두 팀으로 나눠야 합니다. 이것이 가능한지, 가능하다면 두 팀 간 인원 수 차이의 최솟값은 얼마인지 구하세요.

2-coloring

일단 같은 팀이어야 하는 사람들을 하나의 덩어리로 묶고, 다른 팀이어야 하는 사람들의 덩어리를 간선으로 잇습니다. 그러면 2개의 팀으로 사람들을 나눌 수 있음과 이 그래프가 이분 그래프임이 필요충분조건이 됩니다.

같은 팀인 사람들을 묶을 때는 분리 집합을 활용하면 되고, 이분 그래프 판별은 dfs로 쉽게 할 수 있습니다.

간선을 그리는 건 같은 팀끼리 다 묶은 다음에 그리는 게 더 쉬울 것 같은데, 저는 실시간으로 간선을 추가하면서 두 정점을 묶을 때 스투라로 간선도 옮겨주는 방식으로 구현했습니다.

차이 최소화

이분 그래프 상에서 하나의 컴포넌트의 점수를 각 색깔로 칠해진 정점 수의 차이로 생각할 수 있습니다. 우리는 각 컴포넌트의 점수의 부호를 정해서, 그 합의 절댓값이 최소가 되도록 만들어야 합니다.

이는 배낭 DP로 환원되는 문제이며, ${\cal O}(N^2)$에 답을 구할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int par[10101], enemy[10101], col[10101], tmp;
bool vis[10101], d[10101], nd[10101];
vector<int> e[10101];

int f(int x){
	return par[x] <= 0 ? x : par[x] = f(par[x]);
}

void u(int x, int y){
	x = f(x); y = f(y);
	if(x == y) return;
	if(!x || !y) return;
	if(e[x].size() < e[y].size()) swap(x, y);
	for(auto& ee : e[y]) e[x].push_back(ee);
	par[x] += par[y]; par[y] = x;
	
}

int dfs(int now, int c){
	col[now] = c; tmp += c*par[now];
	for(auto nxt : e[now]){
		nxt = f(nxt);
		if(col[now] == col[nxt]) return 0;
		if(!col[nxt] && !dfs(nxt, -c)) return 0;
	}
	return c;
}

int solve(){
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i++) par[i] = -1;
	for(int i = 0; i <= n; i++) enemy[i] = 0;
	for(int i = 1; i <= n; i++) e[i].clear();
	for(int i = 1; i <= n; i++) vis[i] = 0;
	for(int i = 0; i <= n; i++) d[i] = 0;
	for(int i = 0; i <= n; i++) nd[i] = 0;
	for(int i = 1; i <= n; i++) col[i] = 0;
	d[0] = 1;
	while(m--){
		int op, x, y; cin >> op >> x >> y;
		if(op == 1) u(x, y);
		else{
			e[f(x)].push_back(f(y)); e[f(y)].push_back(f(x));
		}
	}

	vector<int> cand;
	for(int i = 1; i <= n; i++) if(f(i) == i && !col[i]){
		tmp = 0;
		if(!dfs(i, 1)) return !(cout << -1 << '\n');
		cand.push_back(abs(tmp));
	}
	int cnt = 0;
	for(auto i : cand){
		for(int j = 0; j <= cnt; j++){
			nd[j+i] |= d[j];
			nd[abs(j-i)] |= d[j];
		}
		cnt += i; assert(cnt <= n);
		for(int j = 0; j <= cnt; j++){
			d[j] = nd[j]; nd[j] = 0;
		}
	}
	for(int i = 0; i <= n; i++) if(d[i]) return !(cout << i << '\n');
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int T = 5; while(T--) solve();
}