当前位置:人工智能 > UVa 1220 Hali-Bula 派对(树 DP,最大独立集)

UVa 1220 Hali-Bula 派对(树 DP,最大独立集)

  • 发布:2023-10-11 16:58

-->

问题:公司有n个人,形成树状结构。除了老板之外,只有一名直接主管。要求尽可能多地选择人员,但不能同时选择一个人和他的直接上级。最多可以选多少人?人,并不是唯一的解决办法。

分析:这道题几乎是最大的树独立集问题,只是多了一个唯一性标准。使用两个数组,一个记录人数,一个判断唯一性。

d[u][0]表示在以u为根的子树中,在不选择u点的情况下可以获得的最大人数,那么d[u][1]表示可以得到的最大人数可以通过选取u点得到。

f[u][0]类似,表示点u在以u为根的子树中是否唯一,那么f[u][1]表示点u是否唯一。

对于d[u][1]的计算,因为选择了u,所以无法选择u的子节点,所以d[u][1] = sum(d[v][0], v为子节点),当 f[v][0] 不唯一时,f[u][1] 也不唯一。

对于d[u][0]的计算,因为u没有被选中,所以它的子节点可以选也可以不选,即选最大的,即d[u][0] = sum( max(d[v][0], d[v][1])), 那么如何判断这个唯一性呢?和上面的差不多了,

还有一个。如果 d[v][0] == d[v][1],那么这不是唯一的。其他的和上面一样。剩下的就简单了,用DFS就可以了。

代码如下:

#包括
#包括
#包括
#包括
#包括 使用命名空间 std;
常量整数 maxn = 200 + 5;
矢量 G[maxn];
bool f[maxn][2];
int d[maxn][2], n, cnt;//d[u][0] 不选 ,d[u][0] 选
地图 ID; void init(){//初始化
for(int i = 1; i <= n; ++i) G[i].clear();
memset(f, false, sizeof(f));
memset(d, 0, sizeof(d));
碳纳米管 = 0; id.clear();
} int getid(const string &s){//获取id
if(id.count(s)) return id[s];
返回 id[s] = ++cnt;
} void dfs(int u){
if(!G[u].size()){//最下端
d[u][0] = 0;
d[u][1] = 1;
返回;
} for(int i = 0; i < G[u].size(); ++i){
int son = G[u][i];
dfs(儿子);
d[u][1] += d[son][0];//d[u][1]的计算
if(f[son][0]) f[u][1] = true;//判断唯一性
if(d[son][0] > d[son][1]){//d[u][0]的计算
d[u][0] += d[son][0];
if(f[son][0]) f[u][0] = true;
}
else if(d[son][0] == d[son][1]){// 那么,那就不唯一
d[u][0] += d[son][0];
f[u][0] = true;
}
否则{
d[u][0] += d[son][1];
if(f[son][1]) f[u][0] = true;
}
}
++d[u][1];//别忘了加1
} int main(){
while(scanf("%d", &n) == 1 && n){
init();
字符串 s1, s2;
cin >> s1; getid(s1);
for(int i = 0; i < n-1; ++i){
cin >> s1 >> s2;
G[getid(s2)].push_back(getid(s1));
} dfs(1);
if(d[1][0] == d[1][1]) printf("%d No\n", d[1][0]);//判断谁的数更大
else if(d[1][0] > d[1][1]) printf("%d %s\n", d[1][0], f[1][0] ? "否" : “是”);
else printf("%d %s\n", d[1][1], f[1][1] ? "否" : "是");
}
返回0;
} -->

相关文章