問題描述

烏拉爾大學的校長打算舉行建校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的結點為根節(jié)點。（一開始沒有注意到，以為根節(jié)點是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;
}