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

电玩女神 2022-06-14 10:18 183阅读 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 条评论，183人围观）

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

相关阅读

相关树形dp入门之poj 2342

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

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

相关 poj2342 树形dp入门

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

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

相关 POJ1417-DP+带权并查集

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

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

相关树状dp Anniversary party

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

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

相关 POJ 2342 Anniversary party(树状DP）

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

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

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

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

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

相关 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 赞/ 220 阅读

相关 UVa 1220 Party at Hali-Bula （树形DP，最大独立集）

题意：公司有 n 个人形成一个树形结构，除了老板都有唯一的一个直系上司，要求选尽量多的人，但不能同时选一人上和他的直系上司，问最多能选多少人，并且是不是唯一的方案。分

向右看齐/ 2021年12月18日 07:39/ 0 赞/ 230 阅读

相关 hdu 2412 Party at Hali-Bula【树形dp】

[HDU 2412][] 　　和[poj 2342（hdu 1520）][poj 2342_hdu 1520]差不多，多了一个判断最优解是(Yes)否(No)唯一。关键问题也

àì夳堔傛蜴生んèń/ 2021年12月15日 04:31/ 0 赞/ 221 阅读

相关 POJ2524 并查集

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

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