本文共 783 字,大约阅读时间需要 2 分钟。
1、
2、题目大意:
有N个人,给出每个人的权值,然后给出他们之间的关系,l k,代表l是员工,k是l的直接上司,现在要求是不让有直接关系的人一块出现在晚会上,求出满足这个要求的人的最大权值是多少。
定义dp[i][0]表示i不选,dp[i][1]表示i选
dp[i][]表示以i为根节点的子树的最大权值和
dp[i][0]=max(dp[j][0],dp[j][1]);//i选时,她的子节点可选可不选,dp[i][0]+=max(dp[j][0],dp[j][1])
dp[i][1]+=dp[j][0];,i结点选,那么他的子节点都不能选
对于这道题来说,首先得建一棵树,可以将给定的关系,存到邻接链表中,使用vector,
#include<vector>
vector<int> adj[N];
如要将v放到以u开头的链中,adj[u].push_back(v);
注意每次使用后,都清空,
for(int i=1;i<=n;i++)
adj[i].clear();
建好树之后,用dfs(),将子节点的值更新到父节点中,最终根节点中的值就是所求,max(dp[u][0],dp[u][1]);
3、AC代码:
#include#include using namespace std;#include #include #define N 6005int num[N];vector adj[N];int indg[N];int dp[N][2];int visit[N];void dfs(int v){ dp[v][0]=0; dp[v][1]=num[v]; visit[v]=1; for(int i=0;i
转载地址:http://yrddi.baihongyu.com/