2875: 没有上司的舞会
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:12
解决:4
题目描述
一个舞会的安排是:如果邀请了某个人,那么一定不会再邀请他的直接的上司,但该人的上司的上司,上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。
已知每个参加晚会的人都有一定的价值,求一个邀请方案,使价值的和最大。
已知每个参加晚会的人都有一定的价值,求一个邀请方案,使价值的和最大。
输入
第$1$行一个整数$N$($1$≤$N$≤$6000$)表示人数。
接下来$N$个整数。表示第$i$个人的价值$x_i$($−128$≤$x$≤$127$)。
接下来每行两个整数$L,K$。表示第$K$个人是第$L$个人的上司。
输入以$0$ $0$结束。
接下来$N$个整数。表示第$i$个人的价值$x_i$($−128$≤$x$≤$127$)。
接下来每行两个整数$L,K$。表示第$K$个人是第$L$个人的上司。
输入以$0$ $0$结束。
输出
一个数,最大的价值和。
样例输入 复制
7
1 1 1 1 1 1 1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
样例输出 复制
5
提示
对于所有数据,保证数据在题面所给范围内。
用f[i][0]存储不选i结点的最优解,f[i][1]存储选i的结点的最优解,具体来说:
(1)当取i点时,他的所有儿子(下属)都不能取,即f[i][1]=sum(f[i.son][0])+i;
(2)不取i点时,可取他的儿子(下属)或不取,即f[i][0]=sum(max(f[i.son][0],f[i.son][1]);
则answer=max(f[root][0],f[root][1])。
题解仅供学习参考。
- 对于测试点weak1~weak5,保证$n$≤$10$。
- 对于测试点6~15,数据随机。
- 对于测试点strong16~20,$n$=$6000$。
- 对于测试点hack1,保证所有xi均为负数
用f[i][0]存储不选i结点的最优解,f[i][1]存储选i的结点的最优解,具体来说:
(1)当取i点时,他的所有儿子(下属)都不能取,即f[i][1]=sum(f[i.son][0])+i;
(2)不取i点时,可取他的儿子(下属)或不取,即f[i][0]=sum(max(f[i.son][0],f[i.son][1]);
则answer=max(f[root][0],f[root][1])。
题解仅供学习参考。
//没有上司的舞会 #include <bits/stdc++.h> using namespace std; int N,f[6001][2],parent[6001]; bool visited[6001]; void Dp(int man) { if(!visited[man]) //没有访问过 { visited[man]=1; for(int i=1; i<=N; i++) if(parent[i]==man) { if(!visited[i]) Dp(i); f[man][1]+=f[i][0]; f[man][0]+=max(f[i][0],f[i][1]); } } } int main() { /*freopen("party.in","r",stdin); freopen("party.out","w",stdout);*/ int man,leader,Max=0; cin>>N; for(int cnt=1; cnt<=N; cnt++) //输入每个人的价值 cin>>f[cnt][1]; while(cin>>man>>leader, man|leader) parent[man]=leader; for(int i=1; i<=N; i++) //保证每个人都被搜索到 Dp(i); for(int i=1; i<=N; i++) //选最优解 Max=max(max(f[i][0],f[i][1]),Max); cout<<Max<<endl; return 0; }