POJ3342 Party at Hali-Bula(树型DP求最大独立集+唯一解判断)-白红宇

POJ3342 Party at Hali-Bula(树型DP求最大独立集+唯一解判断)

阅读量：5889 次

发布时间：2019-06-19

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

题意：

公司参加聚会，要求员工不能和他的上司同时参加，求最多能参加几个人并且判断解是否唯一。

要点：

树型DP的经典题，用dp[u][1]表示选取u的最大值，dp[u][0]表示不选取u的最大值，容易得到状态转移方程为dp[u][1] += dp[v][0]和dp[u][0] += max(dp[v][1], dp[v][0])，可以看到如果dp[u][0]>dp[u][1]时，dp[v][1]==dp[v][0]会造成多解，那么我们最后遍历一遍即可判断是否有多解，还有一种情况是dp[0][1]==dp[0][0]，这当然也有多解。这题用了map，稍微学了一下，还是很好用的。

15573797

Accepted

212K

16MS

1336B

2016-05-31 09:15:14

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          using namespace std;vector
           
             edge[205];int dp[205][2];void dfs(int u,int p){ int i, v; dp[u][0] = 0;//不取当前值 dp[u][1] = 1;//取当前值 for (i = 0; i < edge[u].size(); i++) { int v = edge[u][i]; dfs(v, u); dp[u][1] += dp[v][0]; dp[u][0] += max(dp[v][1], dp[v][0]);//这里状态转移会造成有不唯一的解 }}int main(){ int n,i,j; char boss[200],a[200],b[200]; map
            
              mm; while (scanf("%d", &n), n) { mm.clear(); for (i = 0; i < 205; i++) edge[i].clear(); int tot = 0; scanf("%s", boss); mm[boss] = tot++; for (i = 0; i < n - 1; i++) { scanf("%s%s", a, b); if (mm.find(a) == mm.end()) mm[a] = tot++; if (mm.find(b) == mm.end()) mm[b] = tot++;//如果map中没有b，就把b加入，对应的映射是tot edge[mm[b]].push_back(mm[a]); } dfs(0, 0); bool flag = true; for (i = 0; i < n; i++) { flag = true; if (dp[i][0]>dp[i][1])//只有取dp[i][0]时可能有多解 { for (j = 0; j < edge[i].size(); j++) { if (dp[edge[i][j]][0] == dp[edge[i][j]][1]) { flag = false; break; } } } if (!flag) break; } printf("%d ", max(dp[0][0], dp[0][1])); if (!flag||dp[0][1]==dp[0][0])//还有一种是总体考虑boss要不要选造成的多解 printf("No\n"); else printf("Yes\n"); } return 0;}

转载于:https://www.cnblogs.com/seasonal/p/10343729.html

你可能感兴趣的文章