DDOSvoid's Blog

Luoguu P2465 [SDOI2008]山贼集团

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P2465

Solution

我们注意到产生的影响是从底到根的，所以我们可以在dfs的时候做dp

由于一个节点可以建多个分部，所以我们在dp转移的时候必须枚举子集，具体做法跟背包类似

另外我们dp不需要维护到根的收益，只需要维护到当前节点的收益即可，因为到根的收益与所选点集挂钩，而所选点集已经放到状态里了

时间复杂度 $O(n3^p)$

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 110
#define maxm 13
using namespace std;

int n, m, t, M; 

int c[1 << maxm], g[maxn][maxm]; 

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int f[maxn][1 << maxm], v[1 << maxm]; 
void dfs(int u, int fa) {
    for (int S = 1; S <= M; ++S)
        for (int i = 1; i <= m; ++i)
            if (S >> i - 1 & 1) f[u][S] -= g[u][i]; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dfs(v, u);
        for (int T = M; T; --T)
            for (int S = T; S; S = S - 1 & T)
                f[u][T] = max(f[u][T], f[u][T ^ S] + f[v][S]); 
    }
    for (int S = 1; S <= M; ++S) f[u][S] += v[S]; 
}

int main() { memset(head, -1, sizeof head); 
    cin >> n >> m; M = (1 << m) - 1; 
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x);
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) cin >> g[i][j];
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        int v, o, S = 0; cin >> v >> o;
        for (int j = 1; j <= o; ++j) {
            int x; cin >> x;
            S |= 1 << x - 1; 
        }
        c[S] += v;
    }
    for (int T = 1; T <= M; ++T)
        for (int S = T; S; S = S - 1 & T)
            v[T] += c[S]; 
    dfs(1, 0);
    cout << f[1][M] << endl; 
    return 0;
}