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

题意:

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

分析:

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

 //#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <iostream>
using namespace std; const int maxn = ;
vector<int> sons[maxn];
map<string, int> dict;
int cnt, d[maxn][], f[maxn][]; int ID(const string& s)
{
if(!dict.count(s)) dict[s] = cnt++;
return dict[s];
} int dp(int u, int k) {
f[u][k] = ;
d[u][k] = k;
for(int i = ; i < sons[u].size(); i++) {
int v = sons[u][i];
if(k == ) { //选节点u
d[u][] += dp(v, );
if(!f[v][]) f[u][] = ; //如果子节点v不唯一,则父节点u也不唯一
} else {
d[u][] += max(dp(v, ), dp(v, ));
if(d[v][] == d[v][]) f[u][k] = ;
else if(d[v][] > d[v][] && !f[v][]) f[u][k] = ;
else if(d[v][] > d[v][] && !f[v][]) f[u][k] = ;
}
}
return d[u][k];
} int main(void)
{
#ifdef LOCAL
freopen("1220in.txt", "r", stdin);
#endif int n;
string s, s2;
while(cin >> n >> s)
{
getchar();
cnt = ;
dict.clear();
for(int i = ; i <= n; ++i) sons[i].clear(); //cin >> s;
ID(s);
for(int i = ; i < n; ++i)
{
cin >> s >> s2;
sons[ID(s2)].push_back(ID(s));
}
printf("%d ", max(dp(, ), dp(, )) );
bool unique = false;
if(d[][] > d[][] && f[][]) unique = true;
if(d[][] > d[][] && f[][]) unique = true;
printf("%s\n", unique ? "Yes" : "No");
} return ;
}

代码君

上一篇:使用ExpandoObject来实现多个Model传送至视图


下一篇:Snap即将发布上市后首份财报 广告收入成华尔街关注焦点