[UVa1218][poj3398]-Perfect Service

发布于 2017-09-14  115 次阅读



题目(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;
}