HDU2412 Party at Hali-Bula

一、题目内容

【题目描述】

公司里有n(n<=200)个人形成一个树状结构，即除了老板之外每个员工都有唯一的直属上司。要求选尽量多的人，但不能同时选择一个人和他的直属上司。问：最多能选多少人，以及在人数最多的前提下方案是否唯一。

【输入格式】

第一行一个数n;第二行输入老板的名字;以下的n-1行中,每行是一位员工的名字和其直属上司的名字(英文单词,长度为1到100),两个名字之间有空格隔开,’0’为输入结束的标识符。

【输出格式】

一行,输出一个数字，表示最大的访客数量。并再同一行输出单词’Yes’或’No’，代表目前方案是否唯一。

【输入样例】

6
Jason
Jack Jason
Joe Jack
Jill Jason
John Jack
Jim Jill
2
Ming
Cho Ming
0

【输出样例】

4 Yes
1 No

【测试网站】

HDU2412

二、题目分析

树形DP
用f[i][0]表示不选择i点时，i点及其子树能选出的最多人数，f[i][1]表示选择i点时，i点及其子树的最多人数
状态转移方程:
对于叶子节点 f[k][0] = 0, f[k][1] = 1
对于非叶子节点i,
f[i][0] = ∑ max(f[j][0], f[j][1]) (j是i的儿子)
f[i][1] = 1 + ∑ f[j][0] (j是i的儿子)
最多人数即为max(f[0][0], f[0][1])
如何判断最优解是否唯一?
新加一个状态dup[i][j]，表示相应的f[i][j]是否是唯一方案。
对于叶子结点, dup[k][0] = dup[k][1] = 1.
对于非叶子结点,
对于i的任一儿子j，若(f[j][0] > f[j][1] 且 dup[j][0] == 0) 或 (f[j][0] < f[j][1] 且 dup[j][1] == 0) 或 (f[j][0] == f[j][1])，则dup[i][0] = 0
对于i的任一儿子j有dup[j][0] = 0, 则dup[i][1] = 0

三、代码示例

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200 + 10;
const int INF = 0x3f3f3f3f;

int n;
vector <int> G[maxn];
int f[maxn][2];
bool vis[maxn];
bool ans;
bool dup[maxn][2];

void dfs(int x)
{
  f[x][1] = 1;
  dup[x][1] = dup[x][0] = true;
  for(int i = 0; i < G[x].size(); i++)
  {
    int u = G[x][i];
    if(!vis[u])
    {
     vis[u] = true;
     dfs(u);
     f[x][0] += max(f[u][0],f[u][1]);
     if(f[u][0] > f[u][1] && dup[u][0] == false)
          dup[x][0] = false;
     if(f[u][0] < f[u][1] && dup[u][1] == false)
          dup[x][0] = false;
     if(f[u][0] == f[u][1])
          dup[x][0] = false;
     f[x][1] += f[u][0];
     if(dup[u][0] == false) dup[x][1] = false;
    }
  }
}

int main()
{
  while(scanf("%d",&n) && n)
 {
  map<string,int> mp;
  int tot = 0;
  string boss,u,v;
  cin >> boss;
  mp[boss] = ++tot;
  for(int i = 1; i <= n; i++) G[i].clear();
  for(int i = 1; i < n; i++)
   {
     cin >> u >> v;
     if(mp.count(u) == 0) mp[u] = ++tot;
     if(mp.count(v) == 0) mp[v] = ++tot;
     G[mp[u]].push_back(mp[v]);
     G[mp[v]].push_back(mp[u]);
   }
   memset(f,0,sizeof(f));
   memset(vis,false,sizeof(vis));
   vis[1] = true;
   ans = true;
   dfs(1);
   printf("%d ",max(f[1][0],f[1][1]));
   if(f[1][0] > f[1][1]) ans = dup[1][0];
   else if(f[1][0] < f[1][1]) ans = dup[1][1];
   else ans = false;
   if(ans) printf("Yes\n");
   else printf("No\n");
 }
  return 0;
}