백준18664 Minimums on the Edges

작성일 | In

문제 링크

  • http://icpc.me/18664

사용 알고리즘

  • DP
  • Bitmask

시간복잡도

  • $O(N^2 2^N + NS)$

풀이

$i$번 정점에 붙은 토큰의 개수를 $A_i$, 정점 $U_i, V_i$를 연결하는 간선의 용량을 $B_i = \min(A_{U_i}, A_{V_i})$라고 합시다. 이 문제는 아래 조건을 만족하는 $A_i$를 구하는 문제입니다.

  • $\sum A_i \leq S$ : $\sum A_i < K$라면 아무 정점에 토큰을 더 붙여주면 됩니다.
  • $\sum B_i$를 최대화

집합 $S_i = {v \vert A_v \geq i}$를 정의합시다. 토큰이 1개 이상 붙어있는 정점들을 덮는 덮개, 2개 이상 붙어있는 정점들을 덮는 덮개, …라고 생각하면 편합니다. $A_i$는 $i$번 정점을 포함하는 집합(덮개)의 개수가 됩니다.
또한, $B_i$는 ($U_i$를 포함하는 집합)과 (V_i를 포함하는 집합)의 교집합의 크기 = ($U_i, V_i$를 모두 포함하는 교집합의 크기)가 됩니다.

$f(S_i)$를 집합 $S_i$에 완전히 포함되는 간선의 개수로 정의하면, $\sum B_i = \sum f(S_i)$입니다. 이제 문제의 조건을 다시 정리합시다.

  1. $\sum \vert S_i \vert \leq S$
  2. $S_{i+1} \subset S_i$ : 토큰이 $i+1$개 이상 붙은 정점은 당연히 $i$개 이상 붙어있습니다.
  3. $\sum f(S_i)$를 최대화

2번 조건을 제외하고 1번과 3번 조건만 생각하면, 무게가 $\vert S_i \vert$이고 가치가 $f(S_i)$인 knapsack문제가 됩니다. $2^N$개의 부분집합을 모두 보는 것은 $O(2^NS)$로, 너무 느립니다.
잘 생각해보면, $1 \leq \vert S_i \vert \leq N$이기 때문에, 크기가 $i$이면서 $f(S_i)$가 최대가 되는 $S_i$를 미리 전처리한다면 $O(NS)$에 knapsack문제를 풀 수 있습니다. 크기가 $i$이면서 $f(S_i)$가 최대가 되는 $S_i$는 $O(2^N N^2)$에 구할 수 있습니다.

이렇게 구한 최적해는 2번 조건을 항상 만족합니다.
두 집합 $S_i, S_j$에 대해, $f(S_i) + f(S_j) \leq f(S_i \cup S_j) + f(S_i \cap S_j)$이기 때문에 두 집합이 서로 포함관계에 있는 것이 최적입니다. 그러므로 항상 2번 조건을 만족합니다.

전체 코드

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

typedef long long ll;

int n, m, k, g[22][22], sz[1<<18];
ll fx[1<<18], c[22], val[22], mx;
ll dp[101010]; int prv[101010];

int ans[22];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> k;
    for(int i=0; i<m; i++){
        int s, e; cin >> s >> e; s--; e--;
        g[s][e]++; g[e][s]++;
    }
    for(int bit=0; bit<(1<<n); bit++){
        for(int i=0; i<n; i++) if(bit & (1 << i)) {
            for(int j=i+1; j<n; j++) if(bit & (1 << j)) {
                fx[bit] += g[i][j];
            }
        }
    }
    for(int i=1; i<(1<<n); i++){
        sz[i] = sz[i^(i&-i)]+1;
        if(c[sz[i]] < fx[i]) c[sz[i]] = fx[i], val[sz[i]] = i;
    }

    for(int i=1; i<=n; i++) for(int j=i; j<=k; j++) {
        if(dp[j] < dp[j-i]+c[i]) dp[j] = dp[j-i]+c[i], prv[j] = i;
    }
    int idx = 0, sum = 0;
    for(int i=0; i<=k; i++) if(dp[idx] < dp[i]) idx = i;
    for(int i=idx; i; i-=prv[i]){
        for(int j=0; j<n; j++) if(val[prv[i]] & (1 << j)) ans[j]++, sum++;
    }
    while(sum < k) sum++, ans[0]++;
    for(int i=0; i<n; i++) cout << ans[i] << " ";
}