[CQOI2009] 叶子的颜色 解题报告(树形DP)
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1304
Description
给一棵m个结点的无根树,你可以选择一个度数大于1的结点作为根,然后给一些结点(根、内部结点和叶子均可)着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点(哪怕是这个叶子本身)。 对于每个叶结点u,定义c[u]为从根结点从U的简单路径上最后一个有色结点的颜色。给出每个c[u]的值,设计着色方案,使得着色结点的个数尽量少。
Input
第一行包含两个正整数m, n,其中n是叶子的个数,m是结点总数。结点编号为1,2,…,m,其中编号1,2,… ,n是叶子。以下n行每行一个0或1的整数(0表示黑色,1表示白色),依次为c[1],c[2],…,c[n]。以下m-1行每行两个整数a,b(1<=a < b <= m),表示结点a和b 有边相连。
Output
仅一个数,即着色结点数的最小值。
Sample Input
0
1
0
1 4
2 5
4 5
3 5
Simple Output
HINT
M<=10000
N<=5021
这是一道树形DP
首先我们明确,对于任意一个最优方案,我们都可以把它改变成根节点是染色的情况。什么意思呢?就是我可以把其中某个染色的点改成透明的,然后根节点染色,产生一样的效果。请读者自行画几张图,大概就会明白。
于是我们就得出选任何一个非叶子结点做根其实都是一样的
并且我们设计的DP只需要两个状态就可以了,dp[x][0/1]代表以x为根节点的子树染成0/1的最少染色节点数,状态转移方程如下:
dp[x][1]+=min(dp[e[i].to][1]-1,dp[e[i].to][0])
dp[x][0]+=min(dp[e[i].to][1],dp[e[i].to][0]-1)
若是当前点x染成黑色,那么他的儿子中黑色的点就可以变成透明的,对结果没有影响。白色同理。
如果x是叶子结点,若它的c值代表黑色,则dp[x][1]的最小染色数我们设为inf,这是为了排除这个决策
下面附上代码:
#include<bits/stdc++.h>
using namespace std; const int maxn=+;
const int inf=1e9+;
int m,n,k=;
int head[maxn],c[maxn],dp[maxn][];
struct EDGE
{
int to,next;
}e[maxn];
void add(int u,int v)
{
e[++k].next=head[u];e[k].to=v;head[u]=k;
}
void dfs(int x,int fa)
{
if(x<=n)
{
dp[x][c[x]]=;
dp[x][c[x]^]=inf;
return;
}
dp[x][]=dp[x][]=;
for(int i=head[x];i;i=e[i].next)
{
if(e[i].to==fa) continue;
dfs(e[i].to,x);
dp[x][]+=min(dp[e[i].to][]-,dp[e[i].to][]);
dp[x][]+=min(dp[e[i].to][],dp[e[i].to][]-);
}
}
int main()
{
int ans;
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++)
scanf("%d",&c[i]);
for(int i=;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(n+,);
ans=min(dp[n+][],dp[n+][]);
printf("%d\n",ans);
}
最新文章
- SQL Server 2005 数据库 可疑状态
- JAVA静态代码审查之checkstyle
- 在skyDriver上保存代码
- hdu1863 最小生成树(prim)
- Windows和Unix下的编码问题
- SSH由WAS/Tomcat/Weblogic迁移到JBOSS
- 在WCF中使用消息队列
- forward和redirect 的区别
- thinkphp微信开发之jssdk图片上传并下载到本地服务器
- 升级Android ADT 和SDK
- MSP430F149模拟IIC读写24C02程序
- BZOJ_2460_[BeiJing2011]元素_线性基
- 第33章 密码学(Cryptography),密钥(Keys)和HTTPS - Identity Server 4 中文文档(v1.0.0)
- MySQL数据库表损坏后的修复方法
- 开源组件ELK日志系统配置与管理
- JavaScript大杂烩17 - 性能优化
- Go编写的并行计算示例程序
- create table b1 as select * from b建表锁表测试
- 【Git】从服务器搭建到提交分支使用——初学者轻松上手篇
- 【Python】Flask系列-数据库笔记