题目链接:http://acm.ocrosoft.com/problem.php?cid=1695&pid=7
题目描述:人Ural周立大学的校长正在筹备学校的80周年纪念聚会。由于学校的职员有不同的职务级别,可以构成一棵以校长为根的人事关系树。每个职员都有一个唯一的整数编号(范围在1到N之间),并且对应一个参加聚会所获得的欢乐度。为了使每个参加聚会者都感到欢乐,校长想设法使每个职员和他(她)的直接上司不会同时参加聚会。
你的任务是设计一份参加聚会者的名单,使总的欢乐度最高。
输入
输入的第一行是一个整数N,1<= N <= 6000
以下的N行是对应的N个职员的欢乐度(欢乐度是一个从-128到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
题目类型:
树型dp
思路:
这道题是一道典型的树型dp,我们可以这么理解,如果上司没去,下属可以去或不去,如果上司去了,那下属一定不去,因此我们可以从上到下遍历,将所有情况通过dp的形式遍历出来,得到答案
#include <bits/stdc++.h>
#define maxn 6005
using namespace std;
int m,rt,n,u,v;
int w[maxn];//代表权值
int vis[maxn];//标记根节点
vector<int> g[maxn];
int dp[maxn][2];//二维数组的后一维代表去或不去的两种情况
void dfs(int u)
{
dp[u][0]=0;
dp[u][1]=w[u];//将u去或不去的两种情况分别列出
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
dfs(v);
dp[u][0]+=max(dp[v][1],dp[v][0]);//上司不去,下属可以去可以不去
dp[u][1]+=dp[v][0];//上司去了,下属一定不去
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i];
}
while(~scanf("%d %d",&u,&v))
{
if(u==0&&v==0)
break;
g[v].push_back(u);//建立父节点对子节点的图
vis[u]=1;//标记子节点
}
for(int i=1;i<=n;i++)
{
if(!vis[i])//从根节点开始遍历
{
rt=i;
dfs(rt);
break;
}
}
cout<<max(dp[rt][0],dp[rt][1]);
return 0;
}