树形DP，用数组邻接表空间不够，于是将树转化为二叉树AC
1 #include <iostream>
2 using namespace std;
3 const int maxn=6011;
4 int n;
5 int happy[maxn];
6 int link[maxn][2];
7 int q[maxn],st,en;
8 int f[maxn],g[maxn];
9 bool le[maxn];
10 void bfs(int x){
11 q[++en]=x;
12 while (st<en){
13 ++st;
14 int nx=q[st];
15 int ns=link[nx][0];
16 while (ns!=0){
17 ++en;
18 q[en]=ns;
19 ns=link[ns][1];
20 }
21 }
22 }
23
24 int max(int a,int b){
25 return a>b?a:b;
26 }
27
28 void work(int x){
29 f[x]=happy[x];
30 g[x]=0;
31 int ns=link[x][0];
32 while (ns!=0){
33 f[x]+=g[ns];
34 g[x]+=max(g[ns],f[ns]);
35 ns=link[ns][1];
36 }
37 }
38
39 void init(int a,int b){
40 if (link[a][0]==0) link[a][0]=b;
41 else{
42 int ns=link[a][0];
43 while (link[ns][1]!=0) ns=link[ns][1];
44 link[ns][1]=b;
45 }
46 }
47
48 int main(){
49 scanf("%d",&n);
50 for (int i=1;i<=n;++i) scanf("%d",&happy[i]);
51 int a,b;
52 scanf("%d %d",&a,&b);
53 while (a!=0){
54 init(b,a);
55 le[a]=true;
56 scanf("%d %d",&a,&b);
57 }
58 for (int i=1;i<=n;++i) if (!le[i]) bfs(i);
59 for (int i=n;i>0;--i) work(q[i]);
60 int ans=0;
61 for (int i=1;i<=n;++i) if (!le[i]) ans+=max(f[i],g[i]);
62 cout<<ans;
63 }
64
posted on 2008-11-05 20:34
Joseph 阅读(138)
评论(0) 编辑 收藏 引用