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)有一个不唯一，则不唯一

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <cstdio>

 #include <vector>

 #include <map>

 using namespace std;

 const int MAX = ;

 vector <int> son[MAX];

 map<string, int> name;

 int d[MAX][],f[MAX][];

 void DP(int u)

 {

     if(son[u].size() == )

     {

         d[u][] = f[u][] = ;

         d[u][] = ;

         f[u][] = ;

         return;

     }

     int c = (int) son[u].size();

     for(int i = ; i < c; i++)

     {

         DP(son[u][i]);

     }

     int sum = ,flag = ;

     for(int i = ; i < c; i++)

     {

         sum += d[ son[u][i] ][];

         if(f[ son[u][i] ][] == )

             flag = ;

     }

     if(flag)

         f[u][] = ;

     else

         f[u][] = ;

     d[u][] = max(d[u][], sum + );

     sum = ,flag = ;

     for(int i = ; i < c; i++)

     {

         if(d[ son[u][i] ][] > d[ son[u][i] ][])

         {

             sum += d[ son[u][i] ][] ;

             if(f[ son[u][i] ][] == )

                 flag = ;

         }

         else if(d[ son[u][i] ][] < d[ son[u][i] ][])

         {

             sum += d[ son[u][i] ][];

             if(f[ son[u][i] ][] == )

                 flag = ;

         }

         else

         {

             sum += d[ son[u][i] ][];

             flag = ;

         }

     }

     if(flag)

         f[u][] = ;

     else

         f[u][] = ;

     d[u][] = max(d[u][], sum);

 }

 int main()

 {

     int n,m;

     char worker[],boss[];

     while(scanf("%d", &n) != EOF && n)

     {

         for(int i = ; i < MAX; i++)

             son[i].clear();

         name.clear();

         memset(d, , sizeof(d));

         memset(f, , sizeof(f));

         m = ;

         scanf("%s", boss);

         name[boss] = m++;

         for(int i = ; i < n; i++)

         {

             scanf("%s%s",worker,boss);

             if(name.count(worker) == )  //注意输入的处理

                 name[worker] = m++;

             if(name.count(boss) == )

                 name[boss] = m++;

             son[ name[boss] ].push_back( name[worker] );

         }

         DP();

         if(d[][] > d[][])

         {

             printf("%d ", d[][]);

             if(f[][])

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else if(d[][] < d[][])

         {

             printf("%d ", d[][]);

             if(f[][])

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         else

         {

             printf("%d ", d[][]);

             printf("No\n");

         }

     }

     return ;

 }

巴特西

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

最新文章

热门文章