一道题目

问题描述

长郡中学校长打算举行建校100周年的晚会。学校的职员是分等级的,也就是说职员之间的上下级关系组成一棵以校长为树根的树。校长要亲自邀请一些职员参见晚会。同时校长亲自到场欢庆这个节日。职员用1~n之间的整数编号,人事处给出了每个职员的搞笑指数。如果一个人和他上司一起参加,那么便可能产生麻烦。为了使晚会的每个参加者都高兴,校长不会同时邀请某个职员和他的顶头上司。 你的任务是给出一个客人列表,使得客人的搞笑指数之和最大。

输入

第一行一个整数n(1≤n≤6000)。以下n行每行是相应编号职员的搞笑指数,该数的返回是[-128..127]。然后是职员的关系树,每行格式是<x> <y>,意思是第y个职员是第x个职员的顶头上司。输入以0 0结束。

输出

最大的搞笑指数之和。

题目分析

表示以前几乎就没接触过这种题目是什么鬼…,然后就开始傻逼bfs,然后就爆了。正解:用f[i][0]表示以i为根的子树,且i一定不取所产生的最大权值,用f[i][1]表示以i为根的子树,且i一定取所产生的最大权值,因此对于f[i][1],它的子节点一定不能取,对于f[i][0],它的子节点可以取也可以不取,因此最后的状态转移方程为:$f[i][0]=\sum\limits_{j=1}^{childsize}{\max {f[j][1],f[j][0]}}$.

一般解题方法

  1. 找出所有根节点并入队
  2. 取出队首元素,更新其父亲节点并将其父亲节点入度减1
  3. 判断其父亲节点入度是否为0,若是,则入队
  4. 重复步骤1

贴个代码

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=6000+10;
int x,y,n,a,b,cnt,f[maxn][2],q[maxn],val[maxn],num[maxn],pre[maxn];
int main()
{
	freopen("1.sb","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&val[i]);
	while(cin>>x>>y&&x!=0)
	{
		pre[x]=y;
		num[y]++;
	}
	for(int i=1;i<=n;i++)
		if(num[i]==0)
			q[++cnt]=i;
	for(int k=1;k<=cnt;k++)
	{
		a=q[k];
		f[a][1]+=val[a];
		b=pre[a];
		if(b==0)
			break;
		f[b][1]+=f[a][0];
		f[b][0]+=max(f[a][0],f[a][1]);
		num[b]--;
		if(!num[b])
			q[++cnt]=b;
	}
	printf("%d",f[a][1]);
	return 0;
}