hdu 5834 Magic boy Bi Luo with his excited tree 树形dp

题目大意：给定一个树。给个点有一个值，每个边也有一个值，经过点可以得到点的值(只能拿一次)，边每次经过都要减去边的值。可以理解为点有钱，经过边要交路费，问从每个点开始，得到的值最大是多少。

题解：PS（感觉像是一道以前CF的题，但是找了很久也没有找到） 由于要输出每一个点，所以很自然地想到树形dp。

我们可以先以1为root，以f[i][0]表示在i的子树下返回i所能得到的最大值，以f[i][1]表示在i的子树下不返回i所能得到的最大值。 可以处理掉所有的子树的问题。然而在当前节点与父节点相连时会出现当前边就是父节点（不返回时）最优的走法，所以我们要记录并维护当前（不返回时）次优的解法。（最优和次优必须是无重合的两条路径）。然后再对当前边与f[i][0]和f[i][1]进行分类讨论。代码中g[i]表示返回i点所能得到的最大值,f[i][0]代表不返回i的最大值，f[i][1]代表不返回i的次大值，path记录其对应的是那条边。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
#define maxn 200100
int g[maxn],f[maxn][2],path[maxn][2],val[maxn],v[maxn],n,en;
int first[maxn],nex[maxn],to[maxn];
const int read()
{
    char ch = getchar();
    while (ch<'0' || ch>'9') ch = getchar();
    int x = ch - '0';
    while ((ch = getchar()) >= '0'&&ch <= '9') x = x * 10 + ch - '0';
    return x;
}
void add(int a,int b,int c)
{
    en++;
    to[en]=b;
    nex[en]=first[a];
    first[a]=en;
    val[en]=c;
}
void dfs(int fa,int now)
{
    int u;
    g[now]=v[now];

    path[now][0]=path[now][1]=-1;

    int tmp;

    for(int i=first[now];i;i=nex[i])
    {
        u=to[i];
        if(u==fa) continue;
        dfs(now,u);
        g[now]+=max(0,g[u]-val[i]*2);
    }

    for(int i=first[now];i;i=nex[i])
    {
        u=to[i];
        if(u==fa||f[u][0]<=val[i]) continue;

        tmp=g[now]-max(g[u]-2*val[i],0)+max(f[u][0]-val[i],0);

        if(path[now][0]==-1) path[now][0]=i,f[now][0]=tmp;

        else if (path[now][1]==-1 || f[now][1] < tmp)
        {
            path[now][1]=i; f[now][1]=tmp;

            if (f[now][0] < f[now][1])
                swap(f[now][0],f[now][1]),swap(path[now][0],path[now][1]);
        }
    }
    if (path[now][1] == -1) f[now][1]=g[now];
    if (path[now][0] == -1) f[now][0]=g[now];
}
void dfs2(int fa,int now)
{
    int u;
    int tmp=0,kk=0,flag;
    for(int i=first[now];i;i=nex[i])
    {
        u=to[i];
        if(u==fa) continue;

        f[u][0] = f[u][0] + max(g[now] - max(g[u]-2*val[i],0)-2*val[i],0);
        f[u][1] = f[u][1] + max(g[now] - max(g[u]-2*val[i],0);

        flag = i;

        if(g[u]>=val[i]*2)
        {
            if(path[now][0]!=i) tmp=f[now][0]+val[i];
            else tmp=f[now][1]+val[i];
        }
        else
        {
            if(path[now][0]!=i) tmp=g[u]-val[i]+f[now][0];
            else tmp=g[u]-val[i]+f[now][1];
        }

        if (f[u][1] <= tmp)       swap(f[u][1],tmp),swap(path[u][1],flag);
        if (f[u][0] <= f[u][1]) swap(f[u][0],f[u][1]),swap(path[u][0],path[u][1]);
        g[u]+=max(g[now] - max(g[u]-2*val[i],0);
        dfs2(now,u);
    }
}
int main()
{
    int a,b,c;
    int cas;
    scanf("%d",&cas);
    for(int i=1;i<=cas;i++)
    {
        printf("Case #%d:n",i);
        en=0;
        memset(first,sizeof(first));
        scanf("%d",&n);
        for(int i=1;i<=n;i++) v[i]=read();
        for(int i=1;i<n;i++)
        {
            a=read();
            b=read();
            c=read();
            add(a,c);
            add(b,a,c);
        }
        dfs(0,1);
        dfs2(0,1);
        for(int i=1;i<=n;i++)
        {
            printf("%dn",f[i][0]);
        }
    }
    return 0;
}
/*
1
5
4 1 7 7 7
1 2 6
1 3 1
2 4 8
3 5 2
*/

（编辑：淮安站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!