http://acm.hdu.edu.cn/showproblem.php?pid=1520
1 #include <cstdio> 2 #include <vector> 3 #include <cstring> 4 #include <algorithm> 5 #define maxn 7000 6 using namespace std; 7 8 int dp[maxn][3]; 9 int a[maxn],pre[maxn]; 10 int n,u,v; 11 vector<int>g[maxn]; 12 13 void dfs(int m) 14 { 15 dp[m][1]=a[m]; 16 for(int i=0; i<(int)g[m].size(); i++) 17 { 18 int v2=g[m][i]; 19 dfs(v2); 20 dp[m][0]+=(max(dp[v2][0],dp[v2][1])); 21 dp[m][1]+=dp[v2][0]; 22 } 23 } 24 25 int main() 26 { 27 while(scanf("%d",&n)!=EOF) 28 { 29 memset(a,0,sizeof(a)); 30 memset(pre,-1,sizeof(pre)); 31 memset(dp,0,sizeof(dp)); 32 for(int i=1; i<=n; i++) 33 { 34 g[i].clear(); 35 } 36 for(int i=1; i<=n; i++) 37 { 38 scanf("%d",&a[i]); 39 } 40 int c; 41 while(scanf("%d%d",&u,&v)) 42 { 43 if(u==0&&v==0) break; 44 c=u; 45 g[v].push_back(u); 46 pre[u]=v; 47 } 48 while(pre[c]!=-1) 49 { 50 c=pre[c]; 51 } 52 dfs(c); 53 int ans=max(dp[c][1],dp[c][0]); 54 printf("%d ",ans); 55 } 56 return 0; 57 }