hdu1520 樹形dp
來源：程序員人生 發布時間：2015-05-29 08:27:54 閱讀次數：2717次
每一個節點有權值，子節點和父節點不能同時選，問最后能選的最大價值是多少？
#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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
