树形DP(模板+题目合集)

做了好几天的树形DP的题,没做那种特别难的,感觉类型都差不多,大同小异吧

参考OI WiKi

首先是经典的树形DP题目

洛谷P1352 没有上司的舞会

题目链接:https://www.luogu.com.cn/problem/P1352

某大学有 n个职员,编号为 1~n 。他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数  ,但是呢,如果某个职员的上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数是多少。

可以定义 f[i][0] 表示标号为i的人不去 和 f[i][1] 表示编号为i的人去 时的最优解

转移方程( v 表示 i 节点的子节点)

f[i][0]+ = max(f[v][1] , f[v][0])

f[i][1]+ = f[v][0]

代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    int next,to;
}q[6005];
int f[6005][3],head[10000],book[6005],v[6005];
void dfs(int n)
{
    v[n]=1;
    for(int j=head[n];j!=-1;j=q[j].next)
    {
        if(v[q[j].to]==1)
        {continue;}
        dfs(q[j].to);
        f[n][1]+=f[q[j].to][0];
        f[n][0]+=max(f[q[j].to][1],f[q[j].to][0]);
    }
    return;
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,l,k;
    cin>>n;
    for(int i=1;i<=n;i++)
    {cin>>f[i][1];}
    for(int i=1;i<=n;i++)
    {
        cin>>l>>k;
        q[i].to=l;
        q[i].next=head[k];
        head[k]=i;
        book[l]=1;
    }
    int u;
    for(int i=1;i<=n;i++)
    {
        if(book[i]==0)
        {u=i;dfs(i);break;}
    }
    cout<<max(f[u][1],f[u][0])<<endl;
    return 0;
}

Hdu 2196 Computer

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2196

求树中最长路径

就是对于每个点而言,求出离这个点最远距离的点的距离是多少

PS(因为没看到多组输入WA10多次。。。唉)

做的很多树形DP的题目大都是无根树,即每个点都可以做根

链式前向星存双向边

一般都是先选取一个点做根进行DP,再换根DP,两次dfs

这个题大概也是这个思想吧

对于一个节点,最远距离可能在该节点的子树方向上,也可能在该节点的父节点方向上,两次dfs,第一次求出该节点子树方向上最长距离,第二次求父亲节点方向上的

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MaxSize = 10005;
struct node
{
    ll w,to,next;
}q[10005];
ll head[MaxSize],d[MaxSize][3],idx[MaxSize];
void dfs1(ll n)
{
    ll st[10005],j=0;
    for(int i=head[n];i!=-1;i=q[i].next)
    {
        dfs1(q[i].to);
        d[n][0]=max(d[n][0],d[q[i].to][0]+q[i].w);
        st[j++]=d[q[i].to][0]+q[i].w;
    }
    sort(st,st+j);
    if(j>1)
    {d[n][1]=st[j-2];}
    return ;
}
void dfs2(ll n,ll f,ll w)
{
    if(n!=f)
    {
        ll op=d[n][0]+w;
        if(op==d[f][0])
        {
            d[n][2]=max(d[n][2],d[f][2]+w);
            d[n][2]=max(d[n][2],d[f][1]+w);
        }
        else
        {
            d[n][2]=max(d[n][2],d[f][2]+w);
            d[n][2]=max(d[n][2],d[f][0]+w);
        }
    }
    for(int i=head[n];i!=-1;i=q[i].next)
    {
        dfs2(q[i].to,n,q[i].w);
    }
    return ;
}
int main()
{
    ll n,a,b;
    while(~scanf("%lld",&n)){
    memset(head,-1,sizeof(head));
    memset(d,0,sizeof(d));
    ll cnt=1;
    for(int i=2;i<=n;i++)
    {
        scanf("%lld %lld",&a,&b);
        q[cnt].to=i;
        q[cnt].w=b;
        q[cnt].next=head[a];
        head[a]=cnt;
        cnt++;
    }
    dfs1(1);
    dfs2(1,1,0);
    for(int i=1;i<=n;i++)
    {
        cout<<max(d[i][0],d[i][2])<<endl;
    }
    }
    return 0;
}

Codeforces#627 div.3 F.Maximum White Subtree

也是给你一棵树,树中每个点是白色或黑色,问对于每个点,在包含该点的连通块中白色点数量 - 黑色点数量 最大是多少?

两次dfs,第一次求点的子节点连通方向,第二次换根求父节点方向

代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MaxSize = 200005;
struct node
{
    int to,next;
}q[3*MaxSize];
int a[MaxSize],head[MaxSize],cnt=1,d[MaxSize];
void add(int a,int b)
{
    q[cnt].to=a;
    q[cnt].next=head[b];
    head[b]=cnt;
    cnt++;
}
void dfs(int u,int f)
{
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(v==f)
        {continue;}
        dfs(v,u);
        d[u]=max(d[u],d[v]+d[u]);
    }
    return ;
}
void dfs2(int u,int f)
{
    if(u!=f)
    {
        if(d[u]>=0)
        {d[u]=max(d[u],d[f]);}
        else
        {d[u]=max(d[u],d[u]+d[f]);}
    }
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(v==f)
        {continue;}
        dfs2(q[i].to,u);
    }
    return;
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==0)d[i]=-1;
        else{d[i]=1;}
    }
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d %d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,1);
    dfs2(1,1);
    for(int i=1;i<=n;i++)
    {
        cout<<d[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Poj 1463 Strategic game

最小点覆盖问题(这道题其实是覆盖边)

每个点都可以覆盖其周围的边,求覆盖所有边的最小点数

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
struct node
{
    int to,next;
}q[4000];
int head[4000],cnt=1,d[1800][3];
void add(int a,int b)
{
    q[cnt].to=b;
    q[cnt].next=head[a];
    head[a]=cnt++;
}
void dfs(int u,int f)
{
    int cc=0;
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        if(q[i].to==f)
        {continue;}
        cc++;
    }
    if(cc==0){return;}
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(v==f){continue;}
        dfs(v,u);
        if(d[v][1]==0)
        {d[u][1]=1;}
    }
    return;
}
int main()
{
    int n,c,p,o;
    while(scanf("%d",&n)!=EOF){
    memset(head,-1,sizeof(head));
    memset(d,0,sizeof(d));
    cnt=1;
    for(int k=0;k<n;k++){
    scanf("%d",&o);
    scanf(":(%d)",&c);
    for(int i=1;i<=c;i++)
    {
        scanf("%d",&p);
        add(p,o);add(o,p);
    }}
    dfs(0,0);
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(d[i][1]==1)
        {ans++;}
    }
    printf("%d\n",ans);
    }
    return 0;
}

Poj 3585 Accumulation Degree

最大流

老套路,两次扫描即可

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
using namespace std;
const int Size = 200005;
struct node
{
    int to,w,next;
}q[2*Size];
int head[Size],d[Size],book[Size],cnt;
void add(int a,int b,int c)
{
    q[cnt].to=b;
    q[cnt].w=c;
    q[cnt].next=head[a];
    head[a]=cnt++;
}
void dfs(int u,int f)
{
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(v==f)
        {continue;}
        dfs(v,u);
        if(book[v]==1)
        {d[u]+=q[i].w;}
        else
        {
            if(q[i].w>=d[v])
            {d[u]+=d[v];}
            else
            {d[u]+=q[i].w;}
        }
    }
    return;
}
void dfs2(int u,int f,int w)
{
    if(u!=f)
    {
        int op;
        if(book[f]==1)
        {op=d[f];}
        else
        {op=d[f]-min(d[u],w);}
        d[u]+=min(op,w);
    }
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(v==f){continue;}
        dfs2(v,u,q[i].w);
    }
    return ;
}
int main()
{
    int t,n,a,b,c;
    scanf("%d",&t);
    while(t--)
    {
        memset(head,-1,sizeof(head));
        memset(d,0,sizeof(d));
        memset(book,0,sizeof(book));
        cnt=1;
        scanf("%d",&n);
        for(int i=1;i<=n-1;i++)
        {
            scanf("%d %d %d",&a,&b,&c);
            book[a]++;book[b]++;
            add(a,b,c);add(b,a,c);
        }
        dfs(1,1);
        dfs2(1,1,0);
        int ans=-1;
        for(int i=1;i<=n;i++)
        {ans=max(ans,d[i]);}
        printf("%d\n",ans);
    }
    return 0;
}

待更新~

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注