UVA 1220 题解
题目
链接
题面
自己看链接
题意
一个公司员工要举行聚会，要求任意一个人不能和他的直接上司同时到场，一个员工只有一个支系上司，现在求最多有多少人到场，并且方案是否唯一
题解
思路
水的树形DP入门题。代码满烦的，要记录两种状态的变化：一个是人数的变化，一个是方案是否唯一。且两种方案都有两个子状态：是否取了当前的节点。
代码
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
map<string, int> names;
int str_count = 0;
int get_id(string str)
{
if (!names.count(str))
names[str] = str_count++;
return names[str];
}
vector<vector<int> > data;
vector<vector<int> > f;
vector<vector<bool> > flag;
int n;
void compute(int index)
{
if (f[index][0] || f[index][1])
return;
else
{
if (data[index].empty())
{
f[index][1] = 1;
f[index][0] = 0;
flag[index][1] = true;
flag[index][0] = true;
return;
}
flag[index][0] = true;
flag[index][1] = true;
f[index][1] = 1;
for (int i = 0; i < data[index].size(); i++)
{
compute(data[index][i]);
f[index][0] += max(f[data[index][i]][0], f[data[index][i]][1]);
f[index][1] += f[data[index][i]][0];
if (f[data[index][i]][1] == f[data[index][i]][0] ||
(f[data[index][i]][0] > f[data[index][i]][1] && !flag[data[index][i]][0]) ||
(f[data[index][i]][0] < f[data[index][i]][1] && !flag[data[index][i]][1]))
flag[index][0] = false;
if (flag[data[index][i]][0] == false)
flag[index][1] = false;
}
}
}
int main()
{
while (cin >> n && n)
{
names.clear();
str_count = 0;
data.clear();
f.clear();
flag.clear();
data.resize(n, vector<int>());
for (int i = 0; i < n; i++)
{
string buf1, buf2;
if (i == 0)
{
cin >> buf1;
get_id(buf1);
}
else
{
cin >> buf1 >> buf2;
int to = get_id(buf1);
int from = get_id(buf2);
data[from].push_back(to);
}
}
f.resize(n, vector<int>(2, 0));
flag.resize(n, vector<bool>(2, true));
compute(0);
if (f[0][1] == f[0][0])
{
cout << f[0][1] << " No" << endl;
}
else if (f[0][1] > f[0][0])
{
cout << f[0][1] << " " << (flag[0][1] ? "Yes" : "No") << endl;
}
else
{
cout << f[0][0] << " " << (flag[0][0] ? "Yes" : "No") << endl;
}
}
return 0;
}
