【poj3342】 Party at Hali-Bula-白红宇

【poj3342】 Party at Hali-Bula

阅读量：4504 次

发布时间：2019-06-08

本文共 1805 字，大约阅读时间需要 6 分钟。

(题目链接)

题意

　　给出一棵树，要求在不存在两个节点相邻的条件下，选出尽可能多的节点，并且判断是否有多种选法。

Solution

　　很水的树形dp，2个月前的自己Wa的不要不要的，现在的自己1A。。

　　${f[i][0]}$表示${i}$不去的最大人数，${f[i][1]}$表示${i}$去的最大人数。关键是如何去判断方案的唯一性。

　　对于节点${x}$，我们分情况讨论。

　　1.${x}$去更优。${f[x][1]}$只能由${f[son[x]][0]}$转移过来，那么方案肯定是唯一的，所以我们直接去搜索${son[x]}$的儿子节点。

　　2.${x}$不去更优。${f[x][0]}$能由${f[son[x]][0]}$或者是${f[xon[x]][1]}$转移过来，而如果${f[x][0]}$的值可以由多种方案得到，那么必然是${x}$的某个儿子节点去和不去的人数相等。

　　3.${x}$去与不去的人数相等。那么直接返回1。。

　　至此，问题已经解决。

代码

// poj3342#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #define MOD 100003#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;const int maxn=300;struct edge {int to,next;}e[maxn<<1];map
             
               mp;int head[maxn],f[maxn][2],cnt,n,m;void link(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}void Init() { mp.clear();cnt=n=0; memset(head,0,sizeof(head)); memset(f,0,sizeof(f));}void dfs(int x) { f[x][0]=0;f[x][1]=1; for (int i=head[x];i;i=e[i].next) { dfs(e[i].to); f[x][0]+=max(f[e[i].to][1],f[e[i].to][0]); f[x][1]+=f[e[i].to][0]; }}bool check(int x) { if (f[x][0]==f[x][1]) return 0; if (f[x][0]>f[x][1]) { for (int i=head[x];i;i=e[i].next) if (!check(e[i].to)) return 0; } else { for (int i=head[x];i;i=e[i].next) for (int j=head[e[i].to];j;j=e[j].next) if (!check(e[j].to)) return 0; } return 1;}int main() { while (scanf("%d",&m)!=EOF && m) { Init(); string s1,s2; cin>>s1;mp[s1]=(n=1); for (int i=1;i
              
               >s1>>s2; if (!mp[s1]) mp[s1]=++n; if (!mp[s2]) mp[s2]=++n; link(mp[s2],mp[s1]); } dfs(1); printf("%d %s\n",max(f[1][0],f[1][1]),check(1) ? "Yes" : "No"); } return 0;}

转载于:https://www.cnblogs.com/MashiroSky/p/5928292.html

你可能感兴趣的文章