UVa 1220 (树的最大独立集) Party at Hali-Bula

题意：

有一棵树，选出尽可能多的节点是的两两节点不相邻，即每个节点和他的子节点只能选一个。求符合方案的最大节点数，并最优方案判断是否唯一。

分析：

d(u, 0)表示以u为根的子树中，不选u节点能得到的最大人数，f(u, 0)表示方案是否唯一。

d(u, 1)表示选u节点能得到的最大人数，同理，f(u, 1)表示方案是否唯一。

状态的转移：

- d(u, 1)的计算：因为选了u节点，所以u的子节点都不能选。d(u, 1) = sum{ d(v, 0) | v是u的子节点 }
- f(u, 1)的计算：当且仅当f(v, 0) == 1时，f(u, 1)才是1
- d(u, 0)的计算：因为没有选u节点，所以对于每个子节点v可选可不选。d(u, 0) = sum{ max(d(v, 0), d(v, 1)) }
- f(u, 0)的计算：方案不唯一有两种情况，某个d(v, 1) == d(v, 0) 或者对应取到max方案的f为1

这里用了C++中的map，将字符串与编号对应起来，编写代码比较方便。

 //#define LOCAL

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <string>

 #include <map>

 #include <vector>

 #include <iostream>

 using namespace std;

 const int maxn = ;

 vector<int> sons[maxn];

 map<string, int> dict;

 int cnt, d[maxn][], f[maxn][];

 int ID(const string& s)

 {

     if(!dict.count(s))    dict[s] = cnt++;

     return dict[s];

 }

 int dp(int u, int k) {

   f[u][k] = ;

   d[u][k] = k;

   for(int i = ; i < sons[u].size(); i++) {

     int v = sons[u][i];

     if(k == ) {  //选节点u

       d[u][] += dp(v, );

       if(!f[v][]) f[u][] = ; //如果子节点v不唯一，则父节点u也不唯一

     } else {

       d[u][] += max(dp(v, ), dp(v, ));

       if(d[v][] == d[v][]) f[u][k] = ;

       else if(d[v][] > d[v][] && !f[v][]) f[u][k] = ;

       else if(d[v][] > d[v][] && !f[v][]) f[u][k] = ;

     }

   }

   return d[u][k];

 }

 int main(void)

 {

     #ifdef    LOCAL

         freopen("1220in.txt", "r", stdin);

     #endif

     int n;

     string s, s2;

     while(cin >> n >> s)

     {

         getchar();

         cnt = ;

         dict.clear();

         for(int i = ; i <= n; ++i)    sons[i].clear();

         //cin >> s;

         ID(s);

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

         {

             cin >> s >> s2;

             sons[ID(s2)].push_back(ID(s));

         }

         printf("%d ", max(dp(, ), dp(, )) );

         bool unique = false;

         if(d[][] > d[][] && f[][])    unique = true;

         if(d[][] > d[][] && f[][])    unique = true;

         printf("%s\n", unique ? "Yes" : "No");

     }

     return ;

 }

代码君

巴特西

UVa 1220 (树的最大独立集) Party at Hali-Bula

最新文章

热门文章