周年纪念晚会

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 867 字

人事关系是一棵树，职员与其直接上司不能同时参

一本通
练习

正文

/*
原题：周年纪念晚会（一本通 5.2 练习3）
题意：人事关系是一棵树，职员与其直接上司不能同时参会，求参会最大欢乐度（最大独立集）。
思路：树形 DP。dp[u][0] 不选 u，取儿子最大值之和；dp[u][1] 选 u，累加儿子不选的值。根取最大。
复杂度：O(N) 时间，O(N) 空间。
易错点：欢乐度可能为负，初值取 0 而非负无穷；根为未出现在下属位置的人。
*/
#include <bits/stdc++.h>
using namespace std;
const int N=6005;
vector<int> g[N];
int happy[N];
int dp[N][2];
bool has_boss[N];
void dfs(int u){
    dp[u][0]=0;
    dp[u][1]=happy[u];
    for(int v:g[u]){
        dfs(v);
        dp[u][0]+=max(dp[v][0],dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>happy[i];
    for(int l,k;cin>>l>>k;){
        if(l==0&&k==0)break;
        g[k].push_back(l);
        has_boss[l]=true;
    }
    int root=1;
    while(root<=n&&has_boss[root])root++;
    dfs(root);
    cout<<max(dp[root][0],dp[root][1])<<"\n";
    return 0;
}

周年纪念晚会

正文

一本通·提高篇的其它内容