BZOJ 4033: [HAOI2015]树上染色

Description

有一棵点数为N的树,树边有边权。给你一个在0~N之内的正整数K,你要在这棵树中选择K个点,将其染成黑色,并
将其他的N-K个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。

Input

第一行两个整数N,K。
接下来N-1行每行三个正整数fr,to,dis,表示该树中存在一条长度为dis的边(fr,to)。
输入保证所有点之间是联通的。
N<=2000,0<=K<=N

Output

输出一个正整数,表示收益的最大值。

Sample Input

5 2
1 2 3
1 5 1
2 3 1
2 4 2

Sample Output

17

HINT

将点1,2染黑就能获得最大收益。

Solution

令dp[i][j]表示在i的子树中,钦定j个点黑色后整个子树对全局答案的贡献
然后做树形背包。转移的时候枚举一条边在全局中的贡献即可。
复杂度 \(O(N^2)\)

Code

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 2005;
const int INF = 1000000007;
inline int getint() { int r = 0; bool b = true; char c = getchar(); while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();} while ('0' <= c && c <= '9') {r = (r<<3) + (r<<1) + (c-'0'); c = getchar();} if (b) return r; return -r; }
int siz[maxn], h[maxn], cnte, n, m;
struct edge_t { int to, next; LL w; } edge[maxn<<1];
void ins(int x, int y, LL z) { edge[++cnte].to = y; edge[cnte].next = h[x]; edge[cnte].w = z; h[x] = cnte; }
inline void g(LL &a, const LL &b) { if (a < b) a = b; }
LL dp[maxn][maxn], f_dst[maxn][maxn];
void dfs(int now, int father) {
    LL *f = f_dst[now];
    siz[now] = 1;
    for (int i = h[now]; i; i = edge[i].next) {
        if (edge[i].to == father) continue;
        dfs(edge[i].to, now);
        for (int j = 0; j <= siz[now] + siz[edge[i].to]; ++j) f[j] = -INF;
        for (int j = 0; j <= siz[now]; ++j)
            for (int k = 0; k <= siz[edge[i].to]; ++k)
                g(f[j+k], dp[now][j] + dp[edge[i].to][k] + LL(m-k)*LL(k)*edge[i].w + LL(n-m-(siz[edge[i].to]-k))*LL(siz[edge[i].to]-k)*edge[i].w);
        siz[now] += siz[edge[i].to];
        for (int j = 0; j <= siz[now]; ++j) dp[now][j] = f[j];
    }
}
int main() {
    int x, y; LL z;
    n = getint();
    m = getint();
    for (int i = 1; i < n; ++i) {
        x = getint();
        y = getint();
        z = getint();
        ins(x, y, z);
        ins(y, x, z);
    }
    dfs(1, -1);
    printf("%lld", dp[1][m]);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据