0x54 树形DP

树形DP我只知道千万别写森林转二叉树慢的要死

没有上司的舞会水！裸！

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

struct node

{

    int x,y,next;

}a[];int len,last[];

void ins(int x,int y)

{

    len++;

    a[len].x=x;a[len].y=y;

    a[len].next=last[x];last[x]=len;

}

int f[][],h[];

void treedp(int x)

{

    f[x][]=;f[x][]=h[x];

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        treedp(y);

        f[x][]+=max(f[y][],f[y][]);

        f[x][]+=f[y][];

    }

}

int fa[];

int main()

{

    int n,x,y;

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&h[i]);

    for(int i=;i<n;i++)

    {

        scanf("%d%d",&x,&y);

        ins(y,x);fa[x]=y;

    }

    int rt;

    for(int i=;i<=n;i++)

        if(fa[i]==)rt=i;

    treedp(rt);

    printf("%d\n",max(f[rt][],f[rt][]));

    return ;

}

没有上司的舞会

选课带个背包咯，注意一下背包别重复用一个子节点就好

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

struct node

{

    int x,y,next;

}a[];int len,last[];

void ins(int x,int y)

{

    len++;

    a[len].x=x;a[len].y=y;

    a[len].next=last[x];last[x]=len;

}

int f[][],h[],tot[];

void treedp(int x)

{

    f[x][]=h[x];tot[x]=;

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        treedp(y);

        for(int i=tot[x];i>=;i--)

            for(int j=tot[y];j>=;j--)

                f[x][i+j]=max(f[x][i+j],f[x][i]+f[y][j]);

        tot[x]+=tot[y];

    }

}

int fa[];

int main()

{

    int n,m,x,y;

    scanf("%d%d",&n,&m);

    h[]=;

    for(int i=;i<=n;i++)

    {

        scanf("%d%d",&fa[i],&h[i]);

        ins(fa[i],i);

    }

    memset(f,-,sizeof(f));

    treedp();

    printf("%d\n",f[][m+]);

    return ;

}

选课

poj3585 这题还挺有意思哈，书上说这是“不定根”的树形DP问题，有个很高大上的名词叫二次扫描与换根法

其实自己YY一下，设1为根，第一次dfs把每个点管辖的子树的流量d算出来，对于一个点其实它的流量就是这个d值+从父节点流出去的流量，画个图还是很好解决的，就是min(到父节点的边权，父节点的d值-当前点给父节点的贡献)

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

struct node

{

    int x,y,c,next;

}a[];int len,last[];

void ins(int x,int y,int c)

{

    len++;

    a[len].x=x;a[len].y=y;a[len].c=c;

    a[len].next=last[x];last[x]=len;

}

bool checkleaf(int x,int fr)

{

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        if(y!=fr)return false;

    }

    return true;

}

int d[];

void dfs(int x,int fr)

{

    d[x]=;

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        if(y!=fr)

        {

            dfs(y,x);

            if(checkleaf(y,x)==true)d[x]+=a[k].c;

            else d[x]+=min(a[k].c,d[y]);

        }

    }

}

int mmax;

void solve(int x,int fr,int rd)

{

    mmax=max(mmax,d[x]+rd);

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        if(y!=fr)

        {

            int g;

            if(checkleaf(y,x)==true)g=d[x]-a[k].c;

            else g=d[x]-min(a[k].c,d[y]);

            if(checkleaf(x,y)==true)solve(y,x,a[k].c);

            else solve(y,x,min(rd+g,a[k].c));

        }

    }

}

int main()

{

    freopen("1.in","r",stdin);

    freopen("1.out","w",stdout);

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,x,y,c;

        scanf("%d",&n);

        len=;memset(last,,sizeof(last));

        for(int i=;i<n;i++)

        {

            scanf("%d%d%d",&x,&y,&c);

            ins(x,y,c);ins(y,x,c);

        }

        dfs(,);

        mmax=;solve(,,);

        printf("%d\n",mmax);

    }

    return ;

}

poj3585

巴特西

0x54 树形DP

最新文章

热门文章