UVA1220Party at Hali-Bula(树的最大独立集 + 唯一性判断)

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=105116#problem/H

紫书P282

员工和直属老板只能选一个，最多选多少人

思路：d(u,0)表示以U为根的子树，不选u点，则子节点可选可不选，f(u,0)表示不选u的唯一性（1表示唯一，0,表示不唯一）

d(u,1)以u为根的子树，选择u点，f(u,1)表示选择u的唯一性

转移方程：d(u,0) = sum{ max( d(v,0), d(v,1) ) }，v是子节点，当d(v,0) == d(v,1) ，不唯一，或者选择的那个不唯一，则f（u,0)不唯一

d(u,1) = sum{ d(v,0) }，当f(v,0)有一个不唯一，则不唯一

  1 #include <iostream>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cstdio>
  5 #include <vector>
  6 #include <map>
  7 using namespace std;
  8 const int MAX = 210;
  9 vector <int> son[MAX];
 10 map<string, int> name;
 11 int d[MAX][2],f[MAX][2];
 12 void DP(int u)
 13 {
 14     if(son[u].size() == 0)
 15     {
 16         d[u][1] = f[u][1] = 1;
 17         d[u][0] = 0;
 18         f[u][0] = 1;
 19         return;
 20     }
 21     int c = (int) son[u].size();
 22     for(int i = 0; i < c; i++)
 23     {
 24         DP(son[u][i]);
 25     }
 26     int sum = 0,flag = 0;
 27     for(int i = 0; i < c; i++)
 28     {
 29         sum += d[ son[u][i] ][0];
 30         if(f[ son[u][i] ][0] == 0)
 31             flag = 1;
 32     }
 33     if(flag)
 34         f[u][1] = 0;
 35     else
 36         f[u][1] = 1;
 37     d[u][1] = max(d[u][1], sum + 1);
 38     sum = 0,flag = 0;
 39     for(int i = 0; i < c; i++)
 40     {
 41         if(d[ son[u][i] ][1] > d[ son[u][i] ][0])
 42         {
 43             sum += d[ son[u][i] ][1] ;
 44             if(f[ son[u][i] ][1] == 0)
 45                 flag = 1;
 46         }
 47         else if(d[ son[u][i] ][1] < d[ son[u][i] ][0])
 48         {
 49             sum += d[ son[u][i] ][0];
 50             if(f[ son[u][i] ][0] == 0)
 51                 flag = 1;
 52         }
 53         else
 54         {
 55             sum += d[ son[u][i] ][0];
 56             flag = 1;
 57         }
 58     }
 59     if(flag)
 60         f[u][0] = 0;
 61     else
 62         f[u][0] = 1;
 63     d[u][0] = max(d[u][0], sum);
 64 }
 65 int main()
 66 {
 67     int n,m;
 68     char worker[110],boss[110];
 69     while(scanf("%d", &n) != EOF && n)
 70     {
 71         for(int i = 0; i < MAX; i++)
 72             son[i].clear();
 73         name.clear();
 74         memset(d, 0, sizeof(d));
 75         memset(f, 0, sizeof(f));
 76         m = 0;
 77         scanf("%s", boss);
 78         name[boss] = m++;
 79         for(int i = 1; i < n; i++)
 80         {
 81             scanf("%s%s",worker,boss);
 82             if(name.count(worker) == 0)  //注意输入的处理
 83                 name[worker] = m++;
 84             if(name.count(boss) == 0)
 85                 name[boss] = m++;
 86             son[ name[boss] ].push_back( name[worker] );
 87         }
 88         DP(0);
 89         if(d[0][0] > d[0][1])
 90         {
 91             printf("%d ", d[0][0]);
 92             if(f[0][0])
 93                 printf("Yes
");
 94             else
 95                 printf("No
");
 96         }
 97         else if(d[0][0] < d[0][1])
 98         {
 99             printf("%d ", d[0][1]);
100             if(f[0][1])
101                 printf("Yes
");
102             else
103                 printf("No
");
104         }
105         else
106         {
107             printf("%d ", d[0][0]);
108             printf("No
");
109         }
110     }
111     return 0;
112 }

View Code