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

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

阅读量：5267 次

发布时间：2019-06-14

本文共 1948 字，大约阅读时间需要 6 分钟。

题意：

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

分析：

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，将字符串与编号对应起来，编写代码比较方便。

1 //#define LOCAL 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
           7 #include 
           
             8 #include 
            
              9 using namespace std;10 11 const int maxn = 205;12 vector
             
               sons[maxn];13 map
              
                dict;14 int cnt, d[maxn][2], f[maxn][2];15 16 int ID(const string& s)17 {18 if(!dict.count(s)) dict[s] = cnt++;19 return dict[s];20 }21 22 int dp(int u, int k) {23 f[u][k] = 1;24 d[u][k] = k;25 for(int i = 0; i < sons[u].size(); i++) {26 int v = sons[u][i];27 if(k == 1) { //选节点u28 d[u][1] += dp(v, 0);29 if(!f[v][0]) f[u][1] = 0; //如果子节点v不唯一，则父节点u也不唯一30 } else {31 d[u][0] += max(dp(v, 0), dp(v, 1));32 if(d[v][0] == d[v][1]) f[u][k] = 0;33 else if(d[v][0] > d[v][1] && !f[v][0]) f[u][k] = 0;34 else if(d[v][1] > d[v][0] && !f[v][1]) f[u][k] = 0;35 }36 }37 return d[u][k];38 }39 40 int main(void)41 {42 #ifdef LOCAL43 freopen("1220in.txt", "r", stdin);44 #endif45 46 int n;47 string s, s2;48 while(cin >> n >> s)49 {50 getchar();51 cnt = 0;52 dict.clear();53 for(int i = 0; i <= n; ++i) sons[i].clear();54 55 //cin >> s;56 ID(s);57 for(int i = 1; i < n; ++i)58 {59 cin >> s >> s2;60 sons[ID(s2)].push_back(ID(s));61 }62 printf("%d ", max(dp(0, 0), dp(0, 1)) );63 bool unique = false;64 if(d[0][0] > d[0][1] && f[0][0]) unique = true;65 if(d[0][1] > d[0][0] && f[0][1]) unique = true;66 printf("%s\n", unique ? "Yes" : "No");67 }68 69 return 0;70 }