[SinGuLaRiTy] 树形DP专项测试

【SinGuLaRiTy-1015】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.

对于所有的题目：Time Limit：1s  |  Memory：256 MB

第一题：最长链(HDU 2196 Computer)

题目描述

给定一棵有n个节点的树，求每个节点到其他节点的最大距离。

输入

输入第一行是一个自然数n(n≤10000)；

接下来 (n−1) 行描述：第i行包含两个自然数 , 表示编号为i的节点连接到的节点编号和这条网线的长度..距离总长不会超过10^9. 每行中的两个数字用空格隔开。

输出

输出包含n行. 第i行表示对于离编号为i的节点最远的节点与该节点的距离Si(1≤i≤n)。

样例数据

样例输入	样例输出
3 1 1 1 2	2 3 3

数据规模

30% n≤100

100% n≤10000

题目分析

这道题是考试前一天课上讲的题目，如果我没记错的话应该是HDU 2196的原题。让我兴奋的是，尽管这道题没有被布置进作业当中，但我昨天就已经在HDU上AC了这道题，再打一遍代码也是相当的轻松，一种优越感油然而生......

下面，让我们来看看这道题的思路：对于任何一个节点M，我们可以将距离它最远的点的位置分为两类：①在以M为根节点的子树中，我们假设此种情况下的最远距离为maxdis_down；②在以M为根节点的子树之外,我们假设此种情况下的最远距离为maxdis_up。显而易见的是，此时这个点的最远距离ans[M]就为max(maxdis_down,maxdis_up)。我们重点看看第二种情况：maxdis_up=M到其父亲节点L的距离dis(M,L)+ans[L]。对此，我们可以定义一个dp[MAXN][3]的数组：

f[i][0]表示顶点为i的子树中，距离顶点i的最长距离（对应第一种情况）；

f[i][1]表示i到其父亲节点的距离+其父亲的最长距离（对应第二种情况）；

f[i][0]实际上不需要DP，dfs就可求解（本次dfs也求出次长距离）；对于f[i][1]，我们采取从父节点到子节点的策略。

假设有一L节点，它有n个子节点，我们用Vi来表示。

此时，我们又要分情况来讨论了：

①若Vi不是L的最长路径所经过节点，有f[Vi][1]=dis(Vi,L)+max(f[L][0],f[L][1])；

②若Vi是L的最长路径所经过节点，Vi的最长路径就不能再次被计算，我们就要“退而求其次”，使用第二长的路径Sec_dis，此时有f[Vi][1]=dis(Vi,L)+max(Sec_dis,f[L][1])。

<通过求树的直径解决>

树的直径是什么？就是在一棵树上存在的两点之间的最长距离所经过的路径。例如：

在该图中，树的直径，即距离最长的两点间路径为：7、5、2、1、3、6

在这里我们将用到一个结论：对于任意一个树中的节点来说，距离它最远的点一定是这棵树的直径的两个端点中的一个。【详细证明】

通过这个结论，我们就可以先对两点进行dfs求最远点，确定树的直径的两个端点，然后对树中的点进行dfs求出长度即可。

STD Code

#include<cstring>
#include<cstdio>
#include<algorithm>

#define MAXN 10010

using namespace std;

struct node_a
{
    int head;
}V[MAXN];

struct node_b
{
    int v;
    int w;
    int next;
}E[MAXN];

int top;

void init()
{
    memset(V,-,sizeof(V));
    top=;
}
void add_edge(int u,int v,int w)
{
    E[top].v=v;
    E[top].w=w;
    E[top].next=V[u].head;
    V[u].head=top++;
}
int dp[MAXN][];
void dfs1(int u)
{
    int biggest=,bigger=;
    for(int i=V[u].head;~i;i=E[i].next)
    {
        int v=E[i].v;
        dfs1(v);
        int tmp=dp[v][]+E[i].w;
        if(biggest<=tmp)
        {
            bigger=biggest;
            biggest=tmp;
        }
        else if(bigger<tmp)
        {
            bigger=tmp;
        }
    }
    dp[u][]=biggest;
    dp[u][]=bigger;
}
void dfs2(int u)
{
    for(int i=V[u].head;~i;i=E[i].next)
    {
        int v=E[i].v;
        dp[v][]=max(dp[u][],dp[v][]+E[i].w==dp[u][] ? dp[u][] : dp[u][])+E[i].w;
        dfs2(v);
    }
}
int main()
{int n;
    scanf("%d",&n);
    init();
    for(int v=;v<=n;v++)
    {
        int u,w;
        scanf("%d%d",&u,&w);
        add_edge(u,v,w);
    }
    dfs1();
    dp[][]=;
    dfs2();
    for(int i=;i<=n;i++)
    {
        printf("%d\n",max(dp[i][],dp[i][]));
    }
    return ;
}

第二题：电视转播

题目描述

一个电视网络计划转播一场重要的足球比赛。网络中的传输点和接收点（即用户）可以表示一棵树。这棵树的根是一个传输点，它将转播比赛。树的叶节点是可能要接受这场比赛的用户（他当然可以选择不看比赛，这样就不要交款）。其他非根节点，非叶节点的中间节点为数据的中转站。将一个信号从一个传输点传到另一个传输点的花费是给定的。整个转播的费用就是每一个传输费用的总和。每一个用户（叶节点）都准备付一定的钱来看这场比赛。电视网络公司要决定是否要给这个用户提供电视信号。例如：给一个节点传输信息的花费太大，而他愿意的付款也很少时，网络公司可能选择不给他转播比赛。写一个程序，找到一个传输方案使最多的用户能看到转播比赛，且转播的费用不超过所有接收信号用户的交款。

输入

输入文件的第一行包含两个整数N和M(2<=N<=3000,1<=M<=N-1)。N,M表示分别表示树的节点数和想观看比赛的用户数。树的根节点用1表示，中间节点的标号为2~N-M，用户的节点标号为N-M+1~N。接下来的N-M行表示传输点的信息（依次是节点1，2……）： K A1 C1 A2 C2 …… Ak Ck 表示一个传输点将信号传给K个用户，每一个包含两个数A和C，A表示传输点或用户的节点号，C表示传输的花费。最后一行含有用户的数据，有M个整数表示他们看这场比赛愿意的付费。

输出

仅一行包含一个整数，最大的用户数。

样例数据

样例输入	样例输出
5 3 2 2 2 5 3 2 3 2 4 3 3 4 2	2
5 3 2 2 2 5 3 2 3 2 4 3 4 4 2	3
9 6 3 2 2 3 2 9 3 2 4 2 5 2 3 6 2 7 2 8 2 4 3 3 3 1 1	5

题目分析

注意到了题目结尾处“找到一个传输方案使最多的用户能看到转播比赛，且转播的费用不超过所有接收信号用户的交款”，这种熟悉的感觉——一定是01背包问题,一定是这样的!用户就相当于是物品，传输费用相当于是代价，总交款就是背包的容量......于是，题目类型确定：DP+01背包问题。

定义一个f[MAXN][MAXN]数组，f[l][m]表示：在根节点为l的子树中，将m个用户接入客户端所能得到的最大报酬。DP方程应该是比较好理解的，树形DP套上一个01背包的思路就行了：f[u][j+k]=max(f[u][j+k],f[u][j]+f[v][k]-edge[i].w)

STD Code

#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>

#define MAXN 3010
#define INF 0x3f3f3f3f

using namespace std;

struct node
{
    int v;
    int va;
};

vector <node> tu[MAXN];
int mo[MAXN],f[MAXN][MAXN],get[MAXN];
int n,m;

void add(int u,int v,int va)
{
    node p;
    p.v=v;
    p.va=va;
    tu[u].push_back(p);
}
void init()
{
    int tmp_1,tmp_2,tmp_3;
    scanf("%d%d",&n,&m);
    for(int i=;i<=n-m;i++)
    {
        scanf("%d",&tmp_1);
        for(int j=;j<=tmp_1;j++)
        {
            scanf("%d%d",&tmp_2,&tmp_3);
            add(i,tmp_2,tmp_3);
        }
    }
    for(int i=n-m+;i<=n;i++)
    {
        scanf("%d",&mo[i]);
    }
}
int dp(int x)
{
    if(x>n-m)
    {
        f[x][]=mo[x];
        get[x]=;
        return get[x];
    }
    for(unsigned int i=;i<tu[x].size();i++)
    {
        get[x]+=dp(tu[x][i].v);
    }
    for(unsigned int i=;i<tu[x].size();i++)
    {
        for(int j=get[x];j>=;j--)
        {
            for(int k=min(j,get[tu[x][i].v]);k>=;k--)
            {
                f[x][j]=max(f[x][j],f[tu[x][i].v][k]+f[x][j-k]-tu[x][i].va);
            }
        }
    }
    return get[x];
}
int main()
{
    init();
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
        {
            f[i][j]=-INF;
        }
    dp();
    int ans=;
    for(int i=;i<=m;i++)
    {
        if(f[][i]>=)
        {
            ans=max(ans,i);
        }
    }
    printf("%d",ans);
    return ;
}

第三题：叶子的颜色(CQOI 2009)

题目描述

给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。

对于每个叶结点u，定义c[u]为从根结点到u的简单路径上最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。

输入

第一行包含两个正整数m, n，其中n是叶子的个数，m是结点总数。结点编号为1，2，…，m，其中编号1，2，… ，n是叶子。以下n行每行一个0或1的整数（0表示黑色，1表示白色），依次为c[1]，c[2]，…，c[n]。以下m-1行每行两个整数a，b（1<=a < b <= m），表示结点a和b 有边相连。

输出

仅一个数，即着色结点数的最小值。

样例数据

样例输入	样例输出
5 3 0 1 0 1 4 2 5 4 5 3 5	2

题目分析

在本题当中，题目并没有给出树的根节点，于是首先想到：第一步一定是找根......好吧，这个思路是错的，在最后我们会发现：无论选择哪一个节点作为根，都不会影响答案以及染色状态。比如，当前选择一个节点x为根有最优解，y为它某一个的儿子节点，x和y不会同色——同色必然不为最优解，如果不同色，y转化为x的儿子，这样必然不会影响最优解。

由于发现在一个子树中，不可能存在两个颜色不同的点未满足条件，我们可以进行如下定义：
f[u][0]表示以u为根节点的子树中不存在未满足条件的最小染色节点数；

f[u][1]表示以u为根节点的子树中存在被染色为0的节点不满足条件时的最小染色节点数；

f[u][2]表示以u为根节点的子树中存在被染色为1的节点不满足条件时的最小染色节点数；

对此：tmp_1=∑(f[v][1]);   tmp_2=∑(min(f[v][0],f[v][1]));   tmp_3=∑(min(f[v][0],f[v][2]));

由此可得：f[u][0]=min(tmp_1,tmp_2+1,tmp_3+1);   f[u][1]=min(tmp_2,tmp_3+1);   f[u][2]=min(tmp_2+1,tmp_3);

STD Code

#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>

#define MAXN 10010
#define INF 0x3f3f3f3f

using namespace std;

vector <int> vec[MAXN];

int n,m;
int color,f[MAXN][];
bool vis[MAXN];

void dp(int u)
{
    vis[u]=;
    int tmp_1=,tmp_2=,tmp_3=;
    bool flag=;
    for(unsigned int i=;i<vec[u].size();i++)
    {
        int v=vec[u][i];
        if(vis[v])
            continue;
        dp(v);
        tmp_1+=f[v][];
        tmp_2+=min(f[v][],f[v][]);
        tmp_3+=min(f[v][],f[v][]);
        flag=;
    }
    if(flag)
    {
        f[u][]=min(tmp_1,min(tmp_2+,tmp_3+));
        f[u][]=min(tmp_2,tmp_3+);
        f[u][]=min(tmp_2+,tmp_3);
    }
}
int main()
{
    int u,v;
    scanf("%d%d",&n,&m);
    memset(f,INF,sizeof(f));
    for(int i=;i<=m;i++)
    {
        scanf("%d",&color);
        f[i][]=;
        f[i][color+]=;
    }
    for(int i=;i<=n-;i++)
    {
        scanf("%d%d",&u,&v);
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    dp(n);
    printf("%d\n",f[n][]);
    return ;
}

Time : 2017-04-04