Posted on 2008-08-21 16:03
Hero 閱讀(363)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 // 1039 C++ Accepted 0.015 12 117 KB
2
3 //樹形DP
4 //dp[i][0]表示不選當前節點--dp[i][1]選當前節點
5 //選當前節點的時候不能選兒子節點
6 //沒選當前節點則取選兒子節點和不選兒子節點中的最大值
7 //dp[i][1] = sum( dp[ichild][0] )
8 //dp[i][0] = sum( fmax( dp[ichild][0], dp[ichild][1] ) )
9
10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <string.h>
13
14 const int size = 6010 ;
15 const int INF = 150 * size * -1 ;
16 int dp[size][2] ;
17 int joy[size] ;//歡樂度
18 short edge[size][1000] ;//矩陣模擬鄰接鏈表
19 int outdeg[size] ;
20
21 int inn ;
22
23 int fdp0( int sn ) ;
24 int fdp1( int sn ) ;
25
26
27 int fmax( int a, int b )
28 {
29 return a > b ? a : b ;
30 }
31
32 void input()
33 {
34 for( int i=1; i<=inn; i++ ) scanf( "%d", &joy[i] ) ;
35
36 for( int i=0; i<=inn; i++ ) {
37 edge[i][0] = 0 ;//記錄鏈表個數
38 outdeg[i] = 0 ;
39 }
40
41 int sn, en ;
42 while( true )
43 {
44 scanf( "%d %d", &sn, &en ) ;
45 if( 0==sn && 0==en ) break ;
46 edge[en][++edge[en][0]] = sn ;
47 outdeg[en] ++ ;
48 }//建樹
49 }
50
51 int fdp0( int sn )
52 {
53 if( dp[sn][0]>INF ) return dp[sn][0] ;
54
55 int reval = 0 ;
56 for( int i=1; i<=edge[sn][0]; i++ )
57 {
58 reval += fmax( fdp0(edge[sn][i]), fdp1(edge[sn][i]) ) ;
59 }
60
61 dp[sn][0] = reval ;
62
63 return reval ;
64 }
65
66 int fdp1( int sn )
67 {
68 if( dp[sn][1]>INF ) return dp[sn][1] ;
69
70 int reval = joy[sn] ;
71
72 for( int i=1; i<=edge[sn][0]; i++ )
73 {
74 reval += fdp0( edge[sn][i] ) ;
75 }
76
77 dp[sn][1] = reval ;
78
79 return reval ;
80 }
81
82 void process()
83 {
84 //memset( dp, -1, sizeof(dp) ) ;
85 for( int i=0; i<=inn; i++ ) dp[i][0] = dp[i][1] = INF ;
86
87 for( int i=1; i<=inn; i++ )
88 {
89 if( 0 == outdeg[i] ) { dp[i][0] = 0 ; dp[i][1] = joy[i] ; }
90 }//初始化
91
92 for( int i=1; i<=inn; i++ )
93 {
94 dp[i][0] = fdp0( i ) ;
95 dp[i][1] = fdp1( i ) ;
96 }
97 }
98
99 void output()
100 {
101 int maxjoy = INF ;
102 for( int i=1; i<=inn; i++ )
103 {
104 if( dp[i][0] > maxjoy ) maxjoy = dp[i][0] ;
105 if( dp[i][1] > maxjoy ) maxjoy = dp[i][1] ;
106 }
107
108 printf( "%d\n", maxjoy ) ;
109 }
110
111 int main()
112 {
113 while( scanf( "%d", &inn ) != EOF )
114 {
115 input() ;
116
117 process() ;
118
119 output() ;
120 }
121
122 return 0 ;
123 }