首页 > 其他 > 详细

[HAOI2015]树上染色

时间:2018-10-18 22:47:04      阅读:125      评论:0      收藏:0      [点我收藏+]

题目描述(bzoj)

同上(洛谷)

思路

树形DP
size[i]:i子树的节点个数
f[i][j]:在i子树中染j个黑点的最大贡献
更新时考虑每条边对答案的贡献
即:这条边两侧的黑点个数乘积*边权+两侧白点个数乘积*边权
然后是注意开long long,要不然一半分就没了╮(╯_╰)╭

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 2005
int n,k;
struct edge{
    int u,v,nxt;
    long long dis;
}e[N*2];
int cnt,first[N];
void add_edge(int x,int y,int z){
    e[++cnt].u=x;
    e[cnt].v=y;
    e[cnt].dis=z;
    e[cnt].nxt=first[x];
    first[x]=cnt;
}
bool vis[N];
int size[N];
long long f[N][N];
long long calc(long long dis,int siz,int y){
    dis*=(y*(k-y)+(siz-y)*(n-k-siz+y));
    return dis;
}
void dfs(int u){
    vis[u]=true;
    size[u]=1;
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(!vis[v]){
            dfs(v);
            for(int x=size[u];x>=0;x--){
                for(int y=size[v];y>=0;y--){
                    long long sum=f[u][x]+f[v][y]+calc(e[i].dis,size[v],y);
                    f[u][x+y]=max(f[u][x+y],sum);
//                    printf("when size[%d]=%d,f[%d][%d]=%d\n",u,size[u],x,x+y,f[x][x+y]);
                }
            }
            size[u]+=size[v];
        }
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
        add_edge(y,x,z);
    }
    dfs(1);
    long long ans=f[1][k];
    printf("%lld\n",ans);
    return 0;
}

 

[HAOI2015]树上染色

原文:https://www.cnblogs.com/aptx--4869/p/9813417.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!