【树形DP】洛谷P1352_没有上司的舞会

来源：cnblogs　　作者：Ekretn　　时间：2019/1/21 9:43:17　　对本文有异议

本人第一篇Blog,初学树形DP,心情别样鸡冻...

好了废话不多说,我们来看看题目[传送门]

某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入输出格式

输入格式：

第一行一个整数N。(1<=N<=6000)

接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)

接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。

最后一行输入0 0

输出格式：

输出最大的快乐指数。

样例输入：

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

样例输出：

菜到真实,以泪洗面QAQ

这是一道很经典的树形DP题目,相信我(其实是自己太菜233)

首先我们应该确定一个状态emmm.....

我们以 f[u][1] 表示u号员工回去参加舞会时他的非直属员工的最大快乐值亚索：我听到有人在呼唤我

相对的 f[u][0] 则表示u号员工没有去的最大快乐值。

很容易就可以得到答案便是max(f[root][1],f[root][0])大老板我劝你善良

可以看出每个人和上司之间是可以连一条边的,那么很容易得到下面的一颗树(注意，这里是单向边，因为需要表示上司和部下的关系)

[好用的图论绘图网页你值得拥有]

可以看出5号节点是根节点(记住，在有向图里面这很重要！！！无向图是可以任选一个点作为根节点)，那么怎么找到这颗树的根节点呢？？？

很简单:一个flag标记和读完后一个循环扫描，原理是因为在无向图中根节点是不可能有任何父亲。

1  for(int i=1;i<n;++i) scanf("%d%d",&a,&b),add(b,a),flag[a]==true?:flag[a]=true;//这个地方比较坑的就是存边是b是a的父亲。。。
2  for(int i=1;i<=n;++i) if(!flag[i]) root=i;

好了现在是重头戏——DP部分。。。

思想非常简单，和一般树形DP基本一样

先枚举边，再把边给递归传下去emmm

 1 void dp(int u)
 2 {
 3     for(int i=head[u];i!=-1;i=edge[i].nxt)
 4     {
 5         int v=edge[i].to;
 6         dp(v);
 7         f[u][0]+=max(f[v][1],f[v][0]);
 8         f[u][1]+=f[v][0];
 9     }
10     f[u][1]+=h[u];
11 }

所以,下面给出完整代码:

 1 #include<bits/stdc++.h>
 2 namespace Jason{
 3     inline void scan(int &x){
 4     int f=1;x=0;char s=getchar();
 5     while(s<'0' || s>'9'){if(s=='-') f=-1;s=getchar();}
 6     while(s>='0' && s<='9'){x=x*10+s-'0';s=getchar();}
 7     x*=f;
 8 }
 9     inline void print(int x){
10         if(x<0){putchar('-');x=-x;}
11         if(x>9)print(x/10);char s=x%10+'0';
12         putchar(s);
13     }
14 }
15 using namespace std;
16 using namespace Jason;
17 const int maxn=6000+5;
18 //---------------------以下是数据结构 
19 int n,cnt=0;
20 struct Edge{
21     int to,nxt;//这里用nxt是因为在C++11里面std已经有next了
22 }edge[maxn<<1];int head[maxn];
23 int h[maxn];
24 bool flag[maxn];
25 int f[maxn][2];
26 //----------------------
27 void add(int u,int v){
28     edge[++cnt].nxt=head[u];
29     edge[cnt].to=v;
30     head[u]=cnt;
31 }
32 
33 void dp(int u)
34 {
35     for(int i=head[u];i!=-1;i=edge[i].nxt)
36     {
37         int v=edge[i].to;
38         dp(v);
39         f[u][0]+=max(f[v][1],f[v][0]);
40         f[u][1]+=f[v][0];
41     }
42     f[u][1]+=h[u];
43 }
44 int main(int arrc,char *arrv[])
45 {
46     //freopen("in","r",stdin);
47     memset(head,-1,sizeof(head));
48     int a,b,root;
49     scan(n);
50     for(int i=1;i<=n;++i) scan(h[i]);
51     for(int i=1;i<n;++i) scan(a),scan(b),add(b,a),flag[a]==true?:flag[a]=true;
52     scan(a),scan(b);
53     for(int i=1;i<=n;++i) if(!flag[i]) root=i;//找根节点，因为根节点不可能是任意一个点的儿子 
54     dp(root);
55     print(max(f[root][0],f[root][1]));
56     return 0;
57 }