问题描述

乌拉尔大学的校长打算举行建校80周年的晚会。大学的职员是分等级的，也就是说，职员之间的上下级关系组成了一棵以校长为根的树。职员用1到n之间的整数编号，人事处给出了每个职员的搞笑指数。为了使晚会的每个参加者都高兴，校长不会同时邀请一个职员和他的顶头上司。

你的任务是给出一个客人的列表，使得客人的搞笑指数之和最大。

输入：

第一行是一个整数n（1<=n<=6000）。下面的n行每行是相应职员的搞笑指数。这个数的范围是-128到127。下面是职员的关系数。每行的格式是：<L><K>，意思是第K个职员是第L个职员的顶头上司。输入以0 0结束。

输出：

最大的搞笑指数之和。

此题个人感觉较“计算机网络”更加简单，递推式更容易写出。以d[i][0]表示第i个职员不参加，则以i为根的树可以获得的最大搞笑指数；以d[i][1]表示第i个职员参加，则以i为根的树可以获得的最大搞笑指数。

题目意思即使i若参加，则i的儿子都不参见；若i不参加，i的儿子可参加也可不参加。这样一来递推式很容易写出。

d[i][0]=sum{ max(d[son(i)][0],d[son(i)][1]) };

d[i][1]=fun[i]+sum{ d[son(i)][0] };

此题中还有一个问题，就是关系树中根的不确定。用father[i]=j表示i的父亲为j，则father[i]==0的结点为根节点。（一开始没有注意到，以为根节点是1号结点，结果样例都过不去……）

以下是我的代码：

#include<stdio.h>
#define size 6001
#define max(a,b) (a>b?a:b)
typedef struct NODE
{
    long data;
    struct NODE *next;
}node;
node *son[size];
long n,root,fun[size]={0},father[size]={0},d[size][2]={0};
node* newnode()
{
    node *p;
    p=(node*)malloc(sizeof(node));
    p->data=0;
    p->next=NULL;
    return p;
}
void insert(struct NODE *link,long x)
{// x is link's Son
   node *p;
    p=newnode();
    p->data=x;
    p->next=link->next;
    link->next=p;
}
void init()
{
    FILE *fin=fopen("year.in","r");
    long i,L,K;
    fscanf(fin,"%ld",&n);
    for(i=1;i<=n;i++)
      son[i]=newnode();
    for(i=1;i<=n;i++)
      fscanf(fin,"%ld",&fun[i]);
    fscanf(fin,"%ld%ld",&L,&K);
    while(L!=0||K!=0)
    {
       // L is K's Son,K is L's Father
       father[L]=K;
       insert(son[K],L);
       fscanf(fin,"%ld%ld",&L,&K);
    }
    fclose(fin);
}
void findroot()
{
    long i;
    for(i=1;i<=n;i++)
      if(father[i]==0)
        break;
    root=i;
}
void dp(long k)
{
    long i;
    node *p;
    p=son[k]->next;
    if(p==NULL)
      d[k][1]=fun[k];
    else
    {
       while(p!=NULL)
       {
          dp(p->data);
          d[k][0]+=max(d[p->data][0],d[p->data][1]);
          d[k][1]+=d[p->data][0];
          p=p->next;
       }
       d[k][1]+=fun[k];
    }
}
void write()
{
    FILE *fout=fopen("year.out","w");
    long i,ans;
    ans=max(d[root][0],d[root][1]);
  fprintf(fout,"%ld\n",ans);
    fclose(fout);
}
int main()
{
    init();
    findroot();
    dp(root);
    write();
return 0;
}