codevs 1380 没有上司的舞会

题目描述 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

样例输出 Sample Output

数据范围及提示 Data Size & Hint

各个测试点1s

　　按照这个关系建一棵树，然后进行树归，用f[i]表示i职员参加舞会的最大快乐指数之和，g[i]表示i职员不参加舞会的最大快乐指数之和。那么有f[i]为所有i的子节点的g[son[i]]的和，g[i]是i的子节点的g[son[i]]和f[son[i]]最大值的和。

　　最后的答案在f[1]和g[1]中找最大值。

Code

 /**

  * codevs

  * Problem#1380

  * Accepted

  * Time:10ms

  * Memory:492k

  */

 #include<iostream>

 #include<sstream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cctype>

 #include<cmath>

 #include<ctime>

 #include<map>

 #include<stack>

 #include<set>

 #include<queue>

 #include<vector>

 #ifndef WIN32

 #define AUTO "%lld"

 #else

 #define AUTO "%I64d"

 #endif

 using namespace std;

 typedef bool boolean;

 #define inf 0xfffffff

 #define smin(a, b) (a) = min((a), (b))

 #define smax(a, b) (a) = max((a), (b))

 template<typename T>

 inline boolean readInteger(T& u) {

     char x;

     int aFlag = ;

     while(!isdigit((x = getchar())) && x != '-' && x != -);

     if(x == -)    {

         ungetc(x, stdin);

         return false;

     }

     if(x == '-') {

         aFlag = -;

         x = getchar();

     }

     for(u = x - ''; isdigit((x = getchar())); u = u *  + x - '');

     u *= aFlag;

     ungetc(x, stdin);

     return true;

 }

 typedef class Edge {

     public:

         int end;

         int next;

         Edge(const int end = , const int next = ):end(end), next(next) {        }

 }Edge;

 typedef class MapManager {

     public:

         int ce;

         int *h;

         Edge *edge;

         MapManager():ce(), h(NULL), edge(NULL)    {    }

         MapManager(int points, int edges):ce()    {

             h = new int[(const int)(points + )];

             edge = new Edge[(const int)(edges + )];

             memset(h, , sizeof(int) * (points + ));

         }

         inline void addEdge(int from, int end) {

             edge[++ce] = Edge(end, h[from]);

             h[from] = ce;

         }

         Edge& operator [](int pos) {

             return edge[pos];

         }

 }MapManager;

 #define m_begin(g, i) (g).h[(i)]

 int n;

 int *val;

 MapManager g;

 int *f, *g1;

 int root;

 inline void init() {

     readInteger(n);

     val = new int[(const int)(n + )];

     g = MapManager(n, n);

     f = new int[(const int)(n + )];

     g1 = new int[(const int)(n + )];

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

         readInteger(val[i]);

     int sum = ;

     for(int i = , a, b; i < n; i++) {

         readInteger(a);

         readInteger(b);

         sum += a;

         g.addEdge(b, a);

     }

     root = n * (n + ) /  - sum;

 }

 void treedp(int node, int fa) {

     g1[node] = ;

     f[node] = val[node];

     for(int i = m_begin(g, node); i != ; i = g[i].next) {

         int& e = g[i].end;

         if(e == fa)    continue;

         treedp(e, node);

         g1[node] += max(g1[e], f[e]);

         f[node] += g1[e];

     }

 }

 inline void solve() {

     treedp(root, );

     printf("%d", max(g1[root], f[root]));

 }

 int main() {

     init();

     solve();

     return ;

 }

巴特西

codevs 1380 没有上司的舞会 - 树形动态规划

Code

最新文章

热门文章