백준2453 부서 배치

작성일 | In

문제 링크

  • http://icpc.me/2453

문제 출처

  • 2011 KOI 고등부 2번

사용 알고리즘

  • DP

풀이

각 사람들 사이의 관계는 그래프로 나타낼 수 있습니다. 그래프를 순회하면서 각 그룹의 사람 수를 구해줄 수 있습니다.

각 그룹의 사람들을 두 개의 부서에 적절하게 나눠서 배치해 차이를 최소화해야 하는데, DP로 구해줄 수 있습니다.
dp[n][k] = n번째 그룹까지 고려했을 때 (부서1 - 부서2) = K로 할 수 있는지 여부 처럼 정의를 해주면 쉽게 구할 수 있습니다.
K가 음수가 될 수 있으니 10000정도 더해주면 모두 자연수 범위에서 처리할 수 있습니다.
MLE가 뜰 수 있기 때문에 적절히 토글링을 해주면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll, ll> p;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) { //ax + by = gcd(a, b)
  ll g = a; x = 1, y = 0;
  if (b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
  return g;
}
ll inv(ll a, ll m){ //ax mod m = 1
    ll x, y;
    ll g = ext_gcd(a, m, x, y);
    if(g > 1) return -1;
    return mod(x, m);
}

vector<p> g[10101];
int chk[10101];
int dp[20202];
bool flag;
int cnt;
int n, m;

void dfs(int v, int c){
	if(chk[v]){
		if(chk[v] != c) flag = 1;
		return;
	}
	chk[v] = c;
	if(c == 1) cnt++;
	else cnt--;
	for(auto i : g[v]){
		if(i.y) dfs(i.x, 3-c);
		else dfs(i.x, c);
	}
}

void init(){
	for(int i=0; i<10101; i++) g[i].clear();
	memset(chk, 0, sizeof chk); flag = 0;
	memset(dp, 0, sizeof dp); dp[10000] = 1;
}

void solve(){
	init();
	cin >> n >> m;
	for(int i=0; i<m; i++){
		int s, e, x; cin >> x >> s >> e;
		if(x == 1) x = 0;
		else x = 1;
		g[s].push_back({e, x});
		g[e].push_back({s, x});
	}

	vector<int> v;
	for(int i=1; i<=n; i++){
		if(chk[i]) continue;
		cnt = 0;
		dfs(i, 1);
		if(flag){
			cout << "-1\n"; return;
		}
		v.push_back(abs(cnt));
	}

	for(int i=0; i<v.size(); i++){
		int dp2[20005] = {};
		for(int j=0; j<=20000; j++){
			if(j + v[i] <= 20000) dp2[j] |= dp[j + v[i]];
			if(j >= v[i]) dp2[j] |= dp[j - v[i]];
		}
		for(int j=0; j<=20000; j++){
			dp[j] = dp2[j];
		}
	}
	for(int i=10000; i<20202; i++){
		if(dp[i]){
			cout << i-10000 << "\n"; return;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t = 5; while(t--) solve();
}