题目大意
有一棵树,你需要将N个点染成M种颜色,且需满足一下两种条件
1.一号点必须是一号颜色,且一号颜色必须包含K个点
2.每种颜色必须包含至少一个点
代价为若一条边连接的颜色相同则得付出该边的代价 求满足以上两种情况下的代价之和
DP分析(树形DP+背包)
状态划分f[u][j][0],f[u][j][1];
状态表示f[u][j][0]表当前考虑到u号节点,分给j个大头点,当前节点不被大头吃掉时的最小值
状态计算:
考虑他的子节点v,当子节点v也不被大头吃掉时:
1、m==2,则必定被另外一个头吃掉,加上边权值
2、m>2,则可以被其他头吃掉不需要加上边权值
f[u][j][0]=min(f[u][j][0],min(f[u][j-t][0]+f[v][t][0]+(m==2)*w,f[u][j-t][0]+f[v][t][1]));
状态表示f[u][j][1]表当前考虑到u号节点,分给j个大头点,当前节点被大头吃掉时的最小值
状态计算:
f[u][j][1]=min(f[u][j][1],min(f[u][j-t][1]+f[v][t][1]+w,f[u][j-t][1]+f[v][t][0]));
细节处理
1、这里f[u][j]会被f[u][j-t]更新,采用tmp数组记录一下
2、状态转移时注意m==2且u,v节点都不被大头吃,一定被另外一个节点吃,仍然加上边权值
ac代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int mx=1004;
int n,m,k;
struct node{
int v,next,w;
}eg[mx<<1];
int head[mx<<1],cnt;
void addedge(int u,int v,int w){
eg[++cnt].v=v,eg[cnt].next=head[u],head[u]=cnt,eg[cnt].w=w;
}
int f[mx][mx][2],tmp[mx][2];
/*
状态表示f[u][j][0]表当前考虑到u号节点,分给j个大头点,当前节点不被大头吃掉时的最小值
状态计算:
考虑他的子节点v,当子节点v也不被大头吃掉时:
1、m==2,则必定被另外一个头吃掉,加上边权值
2、m>2,则可以被其他头吃掉不需要加上边权值
f[u][j][0]=min(f[u][j][0],min(f[u][j-t][0]+f[v][t][0]+(m==2)*w,f[u][j-t][0]+f[v][t][1]));
状态表示f[u][j][1]表当前考虑到u号节点,分给j个大头点,当前节点被大头吃掉时的最小值
状态计算:
f[u][j][1]=min(f[u][j][1],min(f[u][j-t][1]+f[v][t][1]+w,f[u][j-t][1]+f[v][t][0]));
*/
void dfs(int u,int fa){
f[u][0][0]=f[u][1][1]=0;
for(int i=head[u];i;i=eg[i].next){
int v =eg[i].v,w=eg[i].w;
if(v==fa) continue;
dfs(v,u);
memcpy(tmp,f[u],sizeof(f[u]));//因为递归更新时f[u][j]会被f[u][j-t]更新,使用tmp数组记录下
memset(f[u],0x3f,sizeof(f[u]));
for(int j=0;j<=k;j++){
for(int t=0;t<=j;t++){
f[u][j][0]=min(f[u][j][0],min(f[v][t][0]+tmp[j-t][0]+(m==2)*w,f[v][t][1]+tmp[j-t][0]));
f[u][j][1]=min(f[u][j][1],min(f[v][t][1]+tmp[j-t][1]+w,f[v][t][0]+tmp[j-t][1]));
}
}
}
}
int main(){
memset(f,0x3f,sizeof(f));
scanf("%d%d%d",&n,&m,&k);//n个苹果,m个头,大头吃k个
for(int i=1,u,v,w;i<n;i++){
cin >> u >> v >> w;
addedge(u,v,w);
addedge(v,u,w);
}
if(m+k-1>n){cout<<-1<<endl;return 0;}
dfs(1,-1);
cout<<f[1][k][1]<<endl;//1号节点必被大头吃
return 0;
}
题目出处
noi2002贪吃的九头蛇