没有上司的舞会（hdu 1520）

题目描述 Description

Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。

输入描述 Input Description

第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。

输出描述 Output Description

输出最大的快乐指数。

样例输入 Sample Input

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

样例输出 Sample Output

数据范围及提示 Data Size & Hint

各个测试点1s

/*

  树形DP

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<vector>

#define M 6010

using namespace std;

int vis[M],in[M],f[M][],n;

vector<int> g[M];

void dfs(int x)

{

    if(vis[x])return;

    vis[x]=;

    for(int i=;i<g[x].size();i++)

    {

        int y=g[x][i];

        dfs(y);

        f[x][]+=max(f[y][],f[y][]);

        f[x][]+=f[y][];

    }

}

void init()

{

    for(int i=;i<=n;i++)

      scanf("%d",&f[i][]);

    while()

    {

        int x,y;

        scanf("%d%d",&x,&y);

        if(x==&&y==)break;

        g[y].push_back(x);

        in[x]++;

    }

    int p=;

    for(int i=;i<=n;i++)

      if(!in[i])

      {

          p=i;

          dfs(i);

          break;

      }

    printf("%d\n",max(f[p][],f[p][]));

    for(int i=;i<=n;i++)

      g[i].clear();

}

int main()

{

    while(scanf("%d",&n)==)

    {

        memset(in,,sizeof(in));

        memset(f,,sizeof(f));

        memset(vis,,sizeof(vis));

        init();

    }

}

巴特西

没有上司的舞会（hdu 1520）

最新文章

热门文章