Party at Hali-Bula UVA - 1220
树形DP基础 求最大独立集
题目描述:老板和员工不能同时选，问最大能选择多少人，并且种种方案是否唯一。
解题分析：定义两个数组 int dp[maxn][2];dp[u][1]表示以u为根节点的子树中选择u能得到的最大人数，dp[u][0]表示不选最大人数
int f[maxn][2];f[u][0]表示以u为根节点的子树，不选u的唯一性f[u][0]表示不选唯一，f[u][1]表示选唯一 .
则求解dp[u][1] = sum{dp[v][0} + 1。 v是U的子节点，只有全部的f[v][0] = 1,f[u][1] 才等于1，其他情况f[u][1] = 0； 求解dp[u][0] = sum(max(dp[v][0],dp[v][1])) , 当存在 dp[v][0] == dp[v][1]时，f[u][0] = 0; 当存在 dp[v][1] > dp[v][0]时，而f[v][1] = 0,此时也是f[u][0] = 0。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
#include <set>
using namespace std;
const int maxn = 200 + 10;
int n;
map<string,int > id;
set<string> getid;
int par[maxn];
vector <int> son[maxn];
int dp[maxn][2];//dp[u][1]表示以u为根节点的子树中选择u能得到的最大人数，dp[u][0]表示不选最大人数
int f[maxn][2];//f[u][0]表示以u为根节点的子树，不选u的唯一性f[u][0]表示不选唯一，f[u][1]表示选唯一
void solve1(int u)
{
int sum = 0;
bool is_uniq = true;
for(int i = 0; i < son[u].size(); i++)
{
int v = son[u][i];
sum += dp[v][0];
if(f[v][0] != 1)
{
is_uniq = false;
}
}
dp[u][1] = sum + 1;
if(is_uniq) f[u][1] = 1;
else f[u][1] = 0;
}
void solve0(int u)
{
int sum = 0;
bool is_uniq = true;
for(int i = 0; i < son[u].size(); i++)
{
int v = son[u][i];
if(dp[v][1] > dp[v][0])
{
sum += dp[v][1];
if(f[v][1] != 1)
{
is_uniq = false;
}
}
else if(dp[v][0] > dp[v][1])
{
sum += dp[v][0];
if(f[v][0] != 1)
{
is_uniq = false;
}
}
else
{
sum += dp[v][0];
is_uniq = false;
}
}
dp[u][0] = sum;
if(is_uniq) f[u][0] = 1;
else f[u][0] = 0;
}
void dfs(int u)
{
if(son[u].size() == 0)
{
dp[u][1] = 1;
f[u][1] = 1;
dp[u][0] = 0;
f[u][0] = 1;
}
else
{
for(int i = 0; i <son[u].size(); i++)
{
int v = son[u][i];
dfs(v);
}
solve1(u);
solve0(u);
}
}
bool deal(int &ans)
{
ans = 0;
int is_uniq;
for(int i = 0; i < n; i++)
{
for(int j = 0; j <= 1; j++)
{
if(dp[i][j] > ans)
{
ans = dp[i][j];
is_uniq = f[i][j];
}
else if(dp[i][j] == ans)
{
is_uniq = 0;
}
}
}
if(is_uniq) return true;
else return false;
}
void init()
{
memset(dp,-1,sizeof(dp));
memset(f,-1,sizeof(f));
for(int i = 0; i < n; i++) son[i].clear();
getid.clear();
id.clear();
string boss;
cin >> boss;
id[boss] = 0;
string x,y;
for(int i = 0; i < n-1 ; i++)
{
cin >> x >> y;
if(!id.count(x))
{
getid.insert(x);
int t = getid.size();
id[x] = t;
}
if(!id.count(y))
{
getid.insert(y);
int t = getid.size();
id[y] = t;
}
par[id[x]] = id[y];
son[id[y]].push_back(id[x]);
}
}
int main()
{
while(cin >> n && n)
{
init();
dfs(0);
int ans;
if(deal(ans)) cout << ans << " Yes" << endl;
else cout << ans << " No" << endl;
}
return 0;
} 代码写的相当矬，但是足够清晰。
查看14道真题和解析
