UVA1218:https://www.luogu.org/problemnew/show/UVA1218
刷紫书DP题ing
思路
参考lrj紫书 不喜勿喷
- d(u,0)：u是服务器，孩子是不是服务器均可
- d(u,1)：u不是服务器，u的父亲是服务器，u的孩子不能是服务器
- d(u,2)：u不是服务器且u的父亲不是服务器，u的孩子必须有且仅有一个是服务器。
前两个状态方程好写
那么d(u,2)呢？
d(u,2)就会等于 他儿子全都不是 减去某个不是 再加上某个是 这是这道树形DP的难点
因此 状态方程：d(u,2) = Min(d(u,1)-d(v,2)+d(v,0)) |v是u的孩子
详细解释见代码~
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
#define maxn 10010
vector<int> sons[maxn];
int dp[maxn][3];
int n;
void search(int u,int father)
{
dp[u][0]=1;//本身算一个
dp[u][1]=0;
dp[u][2]=maxn;//要查找 先定义成最大
for(int i=0;i<sons[u].size();i++)
{
if(sons[u][i]!=father)//如果不是父亲 就是儿子
{
search(sons[u][i],u);//递归查找
dp[u][0]+=min(dp[sons[u][i]][0],dp[sons[u][i]][1]);//如果他是 儿子可以是或者不是
dp[u][1]+=dp[sons[u][i]][2];//如果他不是 但他父亲是 儿子都不是
}
}
for(int i=0;i<sons[u].size();i++)
{
if(sons[u][i]!=father)
dp[u][2]=min(dp[u][1]-dp[sons[u][i]][2]+dp[sons[u][i]][0],dp[u][2]);
//如果他不是 他父亲也不是 那么就是他儿子全都不是减去某个不是再加上某个是
}
}
int main()
{
while(scanf("%d",&n)==1)
{
int x,y;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);//存边
sons[x].push_back(y);
sons[y].push_back(x);
}
search(1,-1);
printf("%d
",min(dp[1][0],dp[1][2]));//答案在第一个是服务器
//或者第一个不是但是儿子之一是
scanf("%d",&x);//数据结束
if(x==-1)
break;
for(int i=1;i<=n;i++)//初始化
sons[i].clear();
memset(dp,0,sizeof(dp));
}
}