首页 > 代码库 > hdu2412（树形dp）
hdu2412（树形dp）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2412
题意：给定一棵关系树 , 从中选择一些点 , 使这些点均不存在亲子关系 , 最多能取多少个点 , 并且判断取法是否唯一 .
分析：如果这题没有判断唯一性，就和hdu1520一样了。设 dp[i][0] 为在以 i 为根的子树中 , 不选择点 i 最多能够选的数目 ,dp[i][1] 为选择 i 点的最多数目 .
状态转移方程 :
当 u 为叶子节点时 :
dp[u][0]=0;
dp[u][1]=1;
当 u 为非叶子节点时 :
dp[u][0]=sum(max(dp[v][0],dp[v][1])) (v 为 u 的儿子 )
dp[u][1]=sum(dp[v][0]) (v 为u 的儿子 )
至于判断唯一性：初始化flag数组全为1，即可行的唯一的。如果父节点以下的某一节点取时不唯一了，递归上去的结果也必定不唯一。
if(dp[v][0]>dp[v][1]&&flag[v][0]==0)flag[u][0]=0;//如果取子节点v即dp[v][0]时而flag[v][0]=0；由于dp[u][0]会取dp[v][0]使得flag[u][0]也变为0，即不唯一了
else if(dp[v][1]>dp[v][0]&&flag[v][1]==0)flag[u][0]=0;;//同理取dp[v][1]时而flag[v][1]=0；由于dp[u][0]会取dp[v][1]使得flag[u][0]也变为0，即不唯一了
else if(dp[v][0]==dp[v][1])flag[u][0]=0;//不唯一的源头
if(flag[v][0]==0)flag[u][1]=0;//由于dp[u][1]必取dp[v][0]，所以flag[v][0]为0的话，flag[u][1]也不唯一了。
#pragma comment(linker,"/STACK:102400000,102400000")#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 210#define FILL(a,b) (memset(a,b,sizeof(a)))using namespace std;struct edge{ int next,v; edge(){} edge(int v,int next):v(v),next(next){}}e[N*2];int head[N],tot;int num,n;int dp[N][2],flag[N][2];void addedge(int u,int v){ e[tot]=edge(v,head[u]); head[u]=tot++;}void dfs(int u,int fa){ dp[u][0]=0;dp[u][1]=1; flag[u][0]=flag[u][1]=1; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(v==fa)continue; dfs(v,u); dp[u][1]+=dp[v][0]; dp[u][0]+=max(dp[v][0],dp[v][1]); if(dp[v][0]>dp[v][1]&&flag[v][0]==0)flag[u][0]=0; else if(dp[v][1]>dp[v][0]&&flag[v][1]==0)flag[u][0]=0; else if(dp[v][0]==dp[v][1])flag[u][0]=0; if(flag[v][0]==0)flag[u][1]=0; }}char str[N],s1[N],s2[N];int main(){ while(scanf("%d",&n)&&n) { tot=0;num=0; map<string,int>mp; FILL(head,-1); scanf("%s",str); mp[str]=++num; for(int i=1;i<n;i++) { scanf("%s%s",s1,s2); if(mp.find(s1)==mp.end())mp[s1]=++num; if(mp.find(s2)==mp.end())mp[s2]=++num; addedge(mp[s1],mp[s2]); addedge(mp[s2],mp[s1]); } dfs(1,-1); if(dp[1][1]>dp[1][0]&&flag[1][1]==1) printf("%d Yes\n",dp[1][1]); else if(dp[1][0]>dp[1][1]&&flag[1][0]==1) printf("%d Yes\n",dp[1][0]); else printf("%d No\n",max(dp[1][0],dp[1][1])); }}
hdu2412（树形dp）