HDU 1520 Anniversary party - dblank

HDU 1520 Anniversary party

<div class="panel_title" align="left">HDU 1520 Anniversary party</div>
<div class="panel_title" align="left">题意:给出一棵树的关系,然后如果一个人的直系上司在的话,就不会去,然后每一个人都有一个参加聚会的快乐度,问最大的快乐度。</div>
<div class="panel_title" align="left">思路:树形dp,dpi表示第i个人去的最大获得值,dpi表示不去的最大获得值,对于i的直系下属来说,如果上司去的话,他就不能去了,就获得不了他的价值。</div>

<div class="panel_title" align="left">

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 6000 + 10, Mod = 1000000000;
typedef long long ll;
struct node
{
    int next, to;
} path[N*100];
int head[N*100], son[N], cnt, n, dpN, w[N], d[N];
void add(int u, int v)
{
    path[cnt].to = v;
    path[cnt].next = head[u];
    head[u] = cnt++;
}
void init()
{
    memset(head, -1, sizeof(head));
    memset(dp, 0, sizeof(dp));
    memset(d, 0, sizeof(d));
}
void dfs(int cur, int s)
{
    int res = 0, sum = 0;;
    for(int i = head[cur]; ~i; i = path[i].next)
    {
        int u = path[i].to;
        if(s == 0)
        {
            dfs(u, 1);
            dfs(u, 0);
            sum += max(dpu, dpu);
        }
        else
        {
            dfs(u, 0);
            res += dpu;
        }
    }
    if(s == 1)
        dpcur = max(dpcur, res + w[cur]);
    else dpcur = sum;
}
int main()
{
    int u, v;
    while(~scanf("%d", &n))
    {
        init();
        for(int i =1; i<=n; i++)
            scanf("%d", &w[i]);
        while(~scanf("%d%d", &u, &v) && (u||v))
        {
            add(v, u);
            d[u]++;
        }
        int start = 0;
        for(int i = 1; i<=n; i++)
        {
            if(d[i] == 0)
            {
                start = i;
                break;
            }
        }
        dfs(start, 0);
        dfs(start, 1);
        cout<<max(dpstart, dpstart)<<endl;
    }
    return 0;
}

</div>
<div class="panel_title" align="left"></div>
<div class="panel_bottom"></div>

相关文章

发表新评论