【树形dp+并查集】Anniversary party POJ - 2342

电玩女神 2022-06-14 10:18 128阅读 0赞

Think:  
1题意：举行聚会，参会人选不希望自己的直属上司参加，关系形成一棵树，参会人选每个人有自己的开心度，求最大开心度  
２思路：树形dp + 并查集（寻找根节点）

[建议参考博客][Link 1]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 6004;
    
    int n, dp[N][2], far[N], vis[N];
    
    void DFS(int u);
    
    int main(){
        int i, s, f, root;
        while(~scanf("%d", &n)){
            memset(dp, 0, sizeof(dp));
            memset(vis, 0, sizeof(vis));
            for(i = 1; i <= n; i++)/*并查集初始化*/
                far[i] = i;
    
            for(i = 1; i <= n; i++)
                scanf("%d", &dp[i][1]);
            while(scanf("%d %d", &s, &f) && (s || f)){
                far[s] = f;
            }
    
            root = 1;
            while(far[root] != root)/*寻找根节点*/
                root = far[root];
    
            DFS(root);
            printf("%d\n", max(dp[root][1], dp[root][0]));
        }
        return 0;
    }
    void DFS(int u){
        vis[u] = 1;
        for(int i = 1; i <= n; i++){
            if((!vis[i]) && far[i] == u){
                DFS(i);
                dp[u][1] += dp[i][0];/*上属去下属不去*/
                dp[u][0] += max(dp[i][1], dp[i][0]);/*上属不去前提下下属去或不去取最大值*/
            }
        }
    }

[Link 1]: http://blog.csdn.net/txl199106/article/details/45372337

发表评论取消回复

表情：

评论列表（有 0 条评论，128人围观）

还没有评论，来说两句吧...

相关阅读

相关树形dp入门之poj 2342

题目：[poj2342Anniversary party][poj2342_Anniversary party] 题意：话说一个公司的一些然要去参加一个party，

向右看齐/ 2022年08月23日 11:53/ 0 赞/ 130 阅读

相关 poj2342 树形dp入门

题意：公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系，求邀请哪些人来能使得晚会的总

心已赠人/ 2022年08月20日 16:06/ 0 赞/ 234 阅读

相关 POJ1417-DP+带权并查集

True Liars <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

Bertha 。/ 2022年07月11日 06:58/ 0 赞/ 117 阅读

相关树状dp Anniversary party

include<cstdio> include<cstring> include<algorithm> include<vector>

ゞ浴缸里的玫瑰/ 2022年06月17日 20:14/ 0 赞/ 121 阅读

相关 POJ 2342 Anniversary party(树状DP）

> Anniversary party > Time Limit: 1000MS Memory Limit: 65536K > Total Submissions: 8

小鱼儿/ 2022年06月16日 10:19/ 0 赞/ 123 阅读

相关【树形dp+并查集】Anniversary party POJ - 2342

Think: 1题意：举行聚会，参会人选不希望自己的直属上司参加，关系形成一棵树，参会人选每个人有自己的开心度，求最大开心度２思路：树形dp + 并查集（寻找根节点）

电玩女神/ 2022年06月14日 10:18/ 0 赞/ 129 阅读

相关 POJ-1182.食物链(并查集)

[1182.食物链][1182.] Description 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有

蔚落/ 2022年03月07日 01:36/ 0 赞/ 201 阅读

相关 POJ-2342.Anniversary party(树形DP)

Description There is going to be a party to celebrate the 80-th Anniversary of the Ur

红太狼/ 2022年03月06日 11:52/ 0 赞/ 161 阅读

相关 POJ2524 并查集

include<iostream> using namespace std; int father[50005]; int rank[50005

曾经终败给现在/ 2021年11月29日 17:32/ 0 赞/ 266 阅读

相关扩展并查集——POJ - 1182

题目含义找出与之前的话不符的假话的数目题目分析简单的扩展并查集题目代码 include<iostream> include<stdio.h>

桃扇骨/ 2021年11月22日 09:28/ 0 赞/ 232 阅读