UVA-1220 Party at Hali-Bula （树的最大独立集）-白红宇

UVA-1220 Party at Hali-Bula （树的最大独立集）

阅读量：4914 次

发布时间：2019-06-11

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

题目大意：数的最大独立集问题。特殊在要求回答答案是否唯一。

题目分析：定义状态dp(i,1),dp(i,0)分别表示以i为根节点的子树选不选i最多可选的人数，f(i,1),f(i,0)分别表示以i为根节点的子树选不选i的方案唯一性。则当选i时，i的子节点都不能选，否则，可选可不选，因此状态转移方程如下：

dp(i,1)=sum(dp(j,0)　　其中，j是i的子节点

dp(i,0)=sum(max(dp(j,1),dp(j,0)))　　其中，j是i的子节点

至于当前状态的唯一性，则受下一步决策的唯一性所影响。

代码如下：

# include
     
      # include
      
       # include
       # include
        
         # include
         
          # include
          
           using namespace std;int n,dp[205][2],f[205][2];string p,q;map
           
            mp;vector
            
             sons[205];int DP(int u,int k){ if(dp[u][k]!=-1) return dp[u][k]; if(sons[u].empty()){ f[u][k]=1; return dp[u][k]=k; } int l=sons[u].size(); int ans=k; if(k==1){ f[u][k]=1;///唯一性受下一步决策的影响 for(int i=0;i
             
              b){ ans+=a; if(f[sons[u][i]][1]==0) f[u][k]=0; }else if(a==b){ ans+=a; f[u][k]=0; }else{ ans+=b; if(f[sons[u][i]][0]==0) f[u][k]=0; } } } return dp[u][k]=ans;}int main(){ while(scanf("%d",&n)&&n) { mp.clear(); memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;++i) sons[i].clear(); int cnt=1; cin>>p; mp[p]=cnt++; for(int i=1;i
              
               >p>>q; if(mp[p]==0) mp[p]=cnt++; if(mp[q]==0) mp[q]=cnt++; sons[mp[q]].push_back(mp[p]); } ///一开始以为大BOSS必须要到场，WA了两次后才意识到大BOSS应该和其他员工一视同仁！！！ int a=DP(1,1),b=DP(1,0); if(a>b){ printf("%d ",a); if(f[1][1]==1) printf("Yes\n"); else printf("No\n"); }else if(a==b){ printf("%d ",a); printf("No\n"); }else{ printf("%d ",b); if(f[1][0]==1) printf("Yes\n"); else printf("No\n"); } } return 0;}

转载于:https://www.cnblogs.com/20143605--pcx/p/4793072.html

你可能感兴趣的文章