題目鏈接:https://vjudge.net/problem/HDU-1520
InputEmployees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go T lines that describe a supervisor relation tree. Each line of the tree specification has the form:?
L K?
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line?
0 0OutputOutput should contain the maximal sum of guests' ratings.?
Sample Input
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
Sample Output
5
題意:在一個有根樹上每個節點有一個權值,每相鄰的父親和孩子只能選擇一個,
問怎么選擇總權值之和最大。
思路:從根出發找,dp[i][0]表示節點i不選,dp[i][1]節點i選。
AC代碼:
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=6010;
vector<int>map[maxn];
int dp[maxn][2],a[maxn],N,vis[maxn];
void dfs(int u){dp[u][0]=0;dp[u][1]=a[u];for(int i=0;i<map[u].size();i++){int v=map[u][i];dfs(v);dp[u][0]+=max(dp[v][0],dp[v][1]);dp[u][1]+=dp[v][0];}
}
int main(){while(~scanf("%d",&N)){for(int i=1;i<=N;i++) scanf("%d",&a[i]);for(int i=1;i<=N;i++) map[i].clear();memset(vis,0,sizeof(vis));int u,v;while(scanf("%d%d",&v,&u)&&u&&v){map[u].push_back(v);vis[v]++; }for(int i=1;i<=N;i++)if(!vis[i]){dfs(i);printf("%d\n",max(dp[i][0],dp[i][1]));break;} }return 0;
}