国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > 综合技术 > hdu1520 树形dp

hdu1520 树形dp

来源:程序员人生   发布时间:2015-05-29 08:27:54 阅读次数:2564次

每一个节点有权值,子节点和父节点不能同时选,问最后能选的最大价值是多少?


#include<cstdio> #include<algorithm> #include<vector> #include<queue> #include<cmath> #include<cstring> using namespace std; typedef long long int64; const int INF = 0x3f3f3f3f; const double PI = acos(⑴.0); const int MAXN = 6010; vector<int>adj[MAXN]; int indeg[MAXN]; int val[MAXN]; int f[MAXN][2]; int n, m; void dfs(int u){ f[u][0] = 0; f[u][1] = val[u]; for(int i=0; i<adj[u].size(); ++i){ int v = adj[u][i]; // if(vis[v]) continue; dfs(v); f[u][0] += max(f[v][1], f[v][0]); f[u][1] += f[v][0]; } } int main(){ while(~scanf("%d", &n) && n){ for(int i=1; i<=n; ++i) adj[i].clear(); for(int i=1; i<=n; ++i) scanf("%d", &val[i]); memset(indeg, 0, sizeof(indeg)); int u, v; while(~scanf("%d%d", &v, &u) && v+u){ adj[u].push_back(v); ++indeg[v]; } memset(f, 0, sizeof(f)); for(int i=1; i<=n; ++i)if(!indeg[i]){ dfs(i); printf("%d ", max(f[i][0], f[i][1])); break; } } return 0; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生