【模板】洛谷P1352_树形dp_拓扑排序实现

问题：结构是森林，含点权，取若干个点（若选择了父节点，则子节点就不能选了），使权值最大

*************************************************************

拓扑排序，从下往上解，并同时记录更新答案

(1)将所有叶子节点push进队列

(2)因为叶子节点的选择与否和其他点没有关系，所以将其处理并更新答案后pop

(3)该叶子节点的fa的son减一，如果该fa的son变为0了，则此时它也为叶子节点，push入队

(4)然后更新该fa的0/1值

(5)重复(2)~(4)直到queue为空

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 6010;
int happy[maxn];//i的快乐值
int fa[maxn], son[maxn];//父亲的编号和儿子的个数
int dp[maxn][2];//i加与不加的快乐值最大值。1表示加，0不加
int main()
{
int i, n, a, b, ans;
memset(dp, 0, sizeof(dp));
memset(son, 0, sizeof(son));
scanf("%d", &n);
for(i = 1; i <= n; ++i) scanf("%d", &happy[i]);
while(scanf("%d %d", &a, &b), a && b)
{
++son[b];
fa[a] = b;
}
queue <int> q;
for(i = 1; i <= n; ++i)//将所有叶子节点入队列
if(!son[i]) q.push(i);
ans = 0;
while(!q.empty())
{
int u = q.front();
q.pop();
//栈中元素0/1对其他元素没影响，先处理并更新
dp[u][1] += happy[u];
ans = max(ans, dp[u][1]);
ans = max(ans, dp[u][0]);
--son[fa[u]];
if(!son[fa[u]]) q.push(fa[u]);
//记录数据
dp[fa[u]][0] = max(dp[fa[u]][0]+dp[u][0], dp[fa[u]][0]+dp[u][1]);
dp[fa[u]][1] += dp[u][0];
}
printf("%dn", ans);
return 0;
}

最后

以上就是糊涂红酒最近收集整理的关于【模板】洛谷P1352_树形dp_拓扑排序实现的全部内容，更多相关【模板】洛谷P1352_树形dp_拓扑排序实现内容请搜索靠谱客的其他文章。