题目（poj）
题目（UVa）
题目（vjudge）
题目大意：
给你一棵树，树上点全是白色。现在把其中一些点染成黑色，使得每个白点都恰好与一个黑点相连。求最少染多少个黑点。
这题作为初级树形dp还是很不错的。
首先，根据树形dp套路，将每个点分成三类：
1.该点为黑点；
2.该点为白点，但它的父亲是黑点；
3.该点为白点，它的父亲也是白点。
对于第1类点，其儿子无论白点黑点都可以；
对于第2类点，其儿子都不能是黑点；
对于第3类点，其儿子中恰有一个为黑点。
于是可以开dp数组了。
设dp[0][u]为第1类点，dp[1][u]为第2类点，dp[2][u]为第3类点。
首先初始化，将第1类点全初始化为1，第2类点全初始化为0，第3类点全初始化为inf。
......啥？为什么要这样处理？
第1类点全是黑点，所以不初始化为1说不过去啊~
第2类点全是白点，而且其父亲又是黑点，所以这一类点一开始必然是0啊~
对于第3类点，往下看
第1类点很好转移，dp[0][u]+=min(dp[0][v],dp[1][v]); /*儿子是黑是白都可以*/
第2类点也很好转移，dp[1][u]+=dp[2][v]; /*儿子是v，父亲是u，u的儿子全是白点，故v全是第3类点*/
第3类点嘛......是枚举哪个儿子成为黑点使其最小......
所以需要全初始化为inf。
但不需要枚举每个儿子，只需要从dp[0][v]，dp[2][v]和dp[1][u]转移过来就行。
......为什么可以这样？
因为将这个点变成黑点，实质上是从当他的儿子作为第2类点时减去这个儿子作为第1类点时中取个最小值。然后加上他作为第1类点的值。
......有点绕，对吧？
然而就是这样的。
所以dp方程为 dp[2][u]=min(dp[2][u],dp[2][v]-dp[0][v]);
然后加个dp[1][u]就行。
具体过程见代码。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf=1e6;
int dp[3][10005];
int scanf0,n;
struct edge{
int vk;
int next;
}e[20005];
int head[10005],t;
int ans;
inline void ad(int u,int v)
{
e[++t].vk=v;
e[t].next=head[u];
head[u]=t;
}
void dfs(int u,int fa)
{
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].vk;
if (v!=fa)
{
dfs(v,u);
dp[0][u]=dp[0][u]+min(dp[0][v],dp[1][v]);
dp[1][u]=dp[1][u]+dp[2][v];
dp[2][u]=min(dp[2][u],dp[0][v]-dp[2][v]);
}
}
dp[2][u]+=dp[1][u];
}
int main()
{
while (~scanf(
{
if (!n) continue;
for (int i=0;i<=n+1;++i)
dp[1][i]=0,dp[0][i]=1,dp[2][i]=inf;
t=0,memset(head,0,sizeof head);
for (int i=1;i<n;++i)
{
int x,y;
scanf(
ad(x,y),ad(y,x);
}
dfs(1,0);
ans=min(dp[0][1],dp[2][1]);
printf(
}
return 0;
}
Comments NOTHING