Algoogle

Algorithm for Programming Contest

Codeforces 440D Berland Federalization

Category: Codeforces Tag: dp, tree

Berland Federalization

問題概要


N(<=400)頂点の木がありその中でちょうどK頂点の連結な部分を取り出した時, その部分とその外の頂点とつながっている辺の数は最小でいくらか.
またその時の辺を答えよ.

解法


問題文は言い換えると木からK頂点の部分木を取り出した時, 最小でいくつの木に分解されるか.
根付き木として考えて,
dp[i][j] := 頂点iを根とする部分木からj頂点の連結な部分を取り出した時の分解される数の最小
とすればよい.
その時の辺は適当にbitsetで持ってdp配列の更新と一緒に更新した.
bitsetのcount()を使えばdp配列もいらないが, どれくらい遅くなるのか不明だったので分けた.
あとは子の部分木についてわかれば, 重さの組を全て試せば良い.

####


(440D.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define pb push_back

const int MAX = 512;
typedef pair<int,int> pii;
vector<pii> G[MAX];
bitset<MAX> ans, bad[MAX][MAX];
int w[MAX], dp[MAX][MAX], acnt, N, K;

void rec(int v, int u){
    w[v] = 1;
    dp[v][0] = dp[v][1] = 0;
    rep(k,G[v].size()){
        int &x = G[v][k].first, &id = G[v][k].second;
        if(x == u) continue;
        bad[x][0][id] = 1;
        rec(x, v);
        int ndp[MAX] = {};
        bitset<MAX> nbad[MAX];
        nbad[0] = bad[v][0];
        repi(i,1,w[v]+1) ndp[i] = dp[v][i]+1, nbad[i] = bad[v][i], nbad[i][id] = 1;
        repi(i,1,w[x]+1) repi(j,1,w[v]+1)
            if(!ndp[i+j] or ndp[i+j] > dp[v][j]+dp[x][i]){
                ndp[i+j] = dp[v][j]+dp[x][i];
                nbad[i+j] = bad[v][j] | bad[x][i];
            }
        w[v] += w[x];
        rep(i,w[v]+1) dp[v][i] = ndp[i], bad[v][i] = nbad[i];
    }
    if(w[v] >= K and acnt > dp[v][K] + (v!=0)) {
        ans = bad[v][K] | bad[v][0];
        acnt = dp[v][K] + (v!=0);
    }
}

void solve(){
    memset(dp,-1,sizeof(dp));
    acnt = N+1;
    rec(0,-1);
    printf("%d\n", acnt);
    rep(i,N) if(ans[i]) printf("%d ", i);
    puts("");
}

void input(){
    scanf("%d%d", &N, &K);
    rep(i,N-1){
        int x, y; scanf("%d%d", &x, &y);
        x--; y--;
        G[x].pb(pii(y,i+1));
        G[y].pb(pii(x,i+1));
    }
}

int main(){
    input();
    solve();
    return 0;
}

Comments