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;
}