UVa1220 - Party at Hali-Bula

网友投稿 633 2022-10-07

UVa1220 - Party at Hali-Bula

UVa1220 - Party at Hali-Bula

题意：一个公司员工要举行聚会，要求任意一个人不能和他的直接上司同时到场，一个员工只有一个支系上司，现在求最多有多少人到场，并且方案是否唯一

分析：分析发现是要求一个树的最大独立集。这里可以用树形dp解决。

定义dp【x】【0】：表示在 i 点不选 i 点的以 x 为子树的最大独立集 而dp【x】【1】 表示x到场的最大独立集

定义f 【x】【0】：表示以x为根且x点不选的子树是否唯一 ，f【x】【1】表示以x为根且x选的子树是否唯一

状态转移方程：dp [ x ] [ 1 ] + = dp [ child ] [ 0 ] ;

dp [ x ] [ 0 ] +  = max ( dp [ child ] [ 0 ] , dp [ child ] [ 1 ] );

而判断唯一性的方程一样的。

#include #include #include #include #include #include #include using namespace std;#define maxn 65540using namespace std;const int inf = 0x3f3f3f3f;const int N = 300;vector child[N];map v;int dp[N][3];bool f[N][3]; //唯一性void DFS(int u){ if(child[u].size()==0) { dp[u][0]=0; dp[u][1]=1; return; } int size=child[u].size(); for(int i=0;idp[child[u][i]][1]) { dp[u][0]+=dp[child[u][i]][0]; if(f[child[u][i]][0]) f[u][0]=1; } else { dp[u][0]+=dp[child[u][i]][1]; if(dp[child[u][i]][1]==dp[child[u][i]][0]||f[child[u][i]][1]) f[u][0]=1; } } dp[u][1]++;}int main(){ int n; while(~scanf("%d",&n) && n) { memset(dp,0,sizeof(dp)); memset(f,0,sizeof(f)); int top = 1; string s1,s2; cin>>s1; v[s1] = top++; for(int i=1;i>s1>>s2; if(!v[s1]) v[s1]=top++; if(!v[s2]) v[s2]=top++; child[v[s2]].push_back(v[s1]); } DFS(1); if(dp[1][1]==dp[1][0]) printf("%d No\n",dp[1][1]); else if(dp[1][1]>dp[1][0]) printf("%d %s\n",dp[1][1],f[1][1]?"No":"Yes"); else printf("%d %s\n",dp[1][0],f[1][0]?"No":"Yes"); for(int i = 1;i<=n;i++) child[i].clear(); v.clear(); } return 0;}

题意：一个公司员工要举行聚会，要求任意一个人不能和他的直接上司同时到场，一个员工只有一个支系上司，现在求最多有多少人到场，并且方案是否唯一

分析：分析发现是要求一个树的最大独立集。这里可以用树形dp解决。

定义dp【x】【0】：表示在 i 点不选 i 点的以 x 为子树的最大独立集 而dp【x】【1】 表示x到场的最大独立集

定义f 【x】【0】：表示以x为根且x点不选的子树是否唯一 ，f【x】【1】表示以x为根且x选的子树是否唯一

状态转移方程：dp [ x ] [ 1 ] + = dp [ child ] [ 0 ] ;

dp [ x ] [ 0 ] +  = max ( dp [ child ] [ 0 ] , dp [ child ] [ 1 ] );

而判断唯一性的方程一样的。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：判断
上一篇:引用传递出现错误
下一篇:微信小程序中选项卡的简单介绍（小程序卡片是什么东西）
相关文章

 发表评论

暂时没有评论，来抢沙发吧~