【POJ2342】Anniversary party(树形动态规划 tree dp)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 05 月 06 日

There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests' conviviality ratings.
大意:很多领导,能形成一个树形关系网,这些领导参加一个party,每个人都有一个能使party活跃的值,但是每个人又不喜欢跟自己的直接领导同时参加party。为使party气氛最好,求最好气氛值。
建树进行深搜,动态规划状态方程:
dp[i][0] += max(dp[i->son][1],dp[i->son][0]);
dp[i][1] += dp[i->son][0];
其中dp[i][0 || 1] 第i个人0表示没去,1表示去了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxlen 6002
int n,dp[maxlen][2],father[maxlen];//0表示不去,1表示去了。
bool visited[maxlen];
void dfs(int node){
	int i,j;
	visited[node] = 1;
	for(i=1;i<=n;i++)
	{
		if(!visited[i]&&father[i] == node)
		{
			dfs(i);
			dp[node][1] += dp[i][0];
			dp[node][0] +=max(dp[i][1],dp[i][0]);
		}
	}
}
int main(){
	freopen("1.txt","r",stdin);
	int i,j;
	int f,c,root;
	while(scanf("%d",&n)!=EOF){
		memset(dp,0,sizeof(dp));
		memset(father,0,sizeof(father));
		memset(visited,0,sizeof(visited));
		for(i=1;i<=n;i++)
			scanf("%d",&dp[i][1]);
		root = 0;
		bool beg = 1;
		while (scanf("%d %d",&c,&f),c+f>0){
			father1 = f;
			if(root == c||beg)
				root = f;
		}
		dfs(root);
		printf("%d\n",max(dp[root][0],dp[root][1]));
	}
}
个人原创,转载请注明:三江小渡

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日