题目描述

blablabla

样例

blablabla

算法1

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>

using namespace std;
const int N=6010;
int n;
int degree[N];
int happy[N];
int dp[N][2];
struct node
{
    int d,w;
};//定义一个结构体来存储每个入度点以及对应边的权值
//比如边u->d,权值为w,node结构体存储的就是d以及w。
vector<node>v[N];
void dfs(int x,int fa){
    dp[x][0]=0;
    dp[x][1]=happy[x];
    vector<node> s=v[x];
    for(int i = 0; i <s.size(); i++)
    {
        int d=s[i].d;
        if(d!=fa){
            dfs(d,x);
        }
        dp[x][0]+=max(dp[d][1],dp[d][0]);
        dp[x][1]+=dp[d][0];
    }
    return;
}
int main()
{
    cin>>n;
    memset(degree, 0, sizeof(degree));
    for (int i = 1; i <=n; ++i) {
        cin>>happy[i];
    }
    int a,b;
    for(int i=0; i<=n; i++)
        v[i].clear();//将vecort数组清空
    for(int i=1; i<=n; i++) //用vector存储邻接表
    {
        node nd;
        cin>>a>>b;
        nd.d=a,nd.w=0;//将入度的点和权值赋值给结构体
        v[b].push_back(nd);//将每一个从b出发能直接到达的点都压到下标为b的vector数组中，以后遍历从b能到达的点就可以直接遍历v[b]
        //        nd.d=a,nd.w=c;//无向图的双向存边
        //        v[b].push_back(nd);
        degree[a]++;
    }
    int root=0;
    //寻找入度为0的点，即是根结点
    for (int i = 1; i <=n; ++i) {
        if(degree[i]==0){
            root=i;
            break;
        }
    }
    dfs(root,0);
    int ans=max(dp[root][1],dp[root][0]);
    cout<<ans<<endl;
    return 0;
}