UVA - 1220 Party at Hali-Bula - c++编程基础

TOP

UVA - 1220 Party at Hali-Bula

2015-11-21 01:01:47 来源: 作者: 【大中小】浏览:1次

题目大意：n 个人形成一个关系树，每个节点代表一个人，节点的根表示这个人的唯一的直接上司，只有根没有上司。要求选取一部分人出来，使得每 2 个人之间不能有直接的上下级的关系，
求最多能选多少个人出来，并且求出获得最大人数的选人方案是否唯一。

解题思路：分析发现是要求一个树的最大独立集。这里可以用树形 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
        using namespace std; string x, y; map 
        
          vis; vector 
         
           A[210]; int n, DP[210][2], flag[210][2]; void init() { for (int i = 0; i <= n; i++) { DP[i][0] = DP[i][1] = 0; flag[i][0] = flag[i][1] = 1; A[i].clear(); } vis.clear(); int top = 1; cin >> x; vis[x] = top++; for (int i = 1; i < n; i++) { cin >> x >> y; if (!vis[x]) vis[x] = top++; if (!vis[y]) vis[y] = top++; A[vis[y]].push_back(vis[x]); } } void DPS(int root) { int num = A[root].size(); for (int i = 0; i < num; i++) { int child = A[root][i]; DPS(child); DP[root][1] += DP[child][0]; DP[root][0] += max(DP[child][0], DP[child][1]); if (DP[child][0] > DP[child][1] && !flag[child][0] || DP[child][0] < DP[child][1] && !flag[child][1] || DP[child][0] == DP[child][1]) flag[root][0] = 0; if (!flag[child][0]) flag[root][1] = 0; } DP[root][1]++; } int main() { while (scanf("%d", &n), n) { init(); DPS(1); printf("%d ", max(DP[1][0], DP[1][1])); if (DP[1][0] > DP[1][1] && flag[1][0]) puts("Yes"); else if (DP[1][1] > DP[1][0] && flag[1][1]) puts("Yes"); else puts("No"); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu 2020 绝对值排序 (java)	下一篇：D. Pair of Numbers Codeforces R..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: