洛谷 P1272 重建道路 解题报告

摘要:
P1272道路重建的主题描述了一场可怕的地震后,人们使用谷仓重建农民的牧场。由于人们没有时间修建额外的道路,从一个谷仓到另一个谷仓的道路是唯一的道路。因此,牧场运输系统可以构建成一棵树。想知道另一场地震会造成多严重的破坏。一旦一些道路被摧毁,包含谷仓的子树将与谷仓的其余部分分离。我想知道这些道路的最小数量。
P1272 重建道路

题目描述

一场可怕的地震后,人们用(N)个牲口棚((1≤N≤150),编号(1..N))重建了农夫(John)的牧场。由于人们没有时间建设多余的道路,所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此,牧场运输系统可以被构建成一棵树。(John)想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏,就会使一棵含有(P(1≤P≤N))个牲口棚的子树和剩余的牲口棚分离,(John)想知道这些道路的最小数目。

输入输出格式

输入格式:

第1行:2个整数,(N)(P)

(2..N)行:每行2个整数(I)(J),表示节点(I)是节点(J)的父节点。

输出格式:

单独一行,包含一旦被破坏将分离出恰含(P)个节点的子树的道路的最小数目。


最近很颓,这个还算裸的树形DP也卡了我好长时间。


首先明确一点(卡了我好久),这是一颗树,根是可以随便选的。

如果只按照题目把树输入是会大的(然而数据水只错了两个点)


(dp[i][j])代表根节点为(i)的子树在失去(注意是失去)(j)个点时 切掉的边的最小个数。

(dp[i][j]=min(dp[i][j],dp[i][j-k]+dp[i_{son}][k]))

  • 注意:这个已经滚动掉了一维(第几个子树) 枚举(j)时要倒着哦

有个问题,对于直接切掉自己儿子的情况怎么办?

最开始时我这样做了,在每次枚举(j)的时候

(dp[i][j]=min(dp[i][j],dp[i][j-size[i_{son}]]+1);)

然而这样做是重复了的。(想想看)

有个很喵(妙)的做法。

(dfs)每次求完(i)时把她自己切掉就好了啦 -> (dp[i][size[i]]=1);

回到最开始,虽然根不确定,其实只需要随便取一种根的情况就行拉。

比如说(root)是根,(dp[root][n-p])肯定不包含切她自己的情况

我们就在其他节点中,把自己切成一棵树,即用(dp[i][p-(n-size[i])]+1)更新(ans)

#include <cstdio>
#include <cstring>
int min(int x,int y) {return x<y?x:y;}
const int N=156;
int dp[N][N];//子树i舍弃j个点的最小切割数
int n,p,root;
int g[N][N],used[N],size[N];

void dfs(int now)
{
    dp[now][0]=0;
    for(int i=1;i<=n;i++)//枚举子树
        if(g[now][i])
        {
            dfs(i);
            size[now]+=size[i];
            int r=min(p,size[now]);
            for(int j=r;j>=1;j--)//枚举当前舍弃节点数
            {
                int r2=min(min(p,size[i]),j);
                for(int k=1;k<=r2;k++)//枚举子树状态
                    dp[now][j]=min(dp[now][j],dp[now][j-k]+dp[i][k]);
            }
        }
    dp[now][++size[now]]=1;
}

int main()
{
    memset(dp,0x3f,sizeof(dp));
    scanf("%d%d",&n,&p);
    int u,v;
    p=n-p;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        g[u][v]=1;
        used[v]=1;
    }
    for(int i=1;i<=n;i++)
        if(!used[i])
        {
            root=i;
            break;
        }
    dfs(root);
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        if(i==root) {ans=min(ans,dp[i][p]);continue;}
        int tt=p+size[i]-n;//还要砍得
        if(tt>=0) ans=min(ans,dp[i][tt]+1);
    }
    printf("%d
",ans);
    return 0;
}

2018.5.6

免责声明:文章转载自《洛谷 P1272 重建道路 解题报告》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇洛谷 P2764 最小路径覆盖问题 解题报告grep正则表达式(二)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

再说MVC

MVC是什么?多层构架又是什么? 首先不要把这两个东西混在一起,它们是两个东西,首先说一个多层构架,它一般指将项目分为三个层次进行开发,即UI(WEB)表示层,BLL(Service)业务层和DAL(Data)数据访问层,它是一种开发项目的模式,也是多人开发的一种最好的选择;而MVC它是建立在UI(WEB)表示层中的一种将代码与页面分层和对URL优化的一种方...

图形图像显示研究(二)

作者:朱金灿来源:http://blog.csdn.net/clever101 前言:继续更新我的图像显示研究方面的文章。 今天草拟了一个研究提纲: 1.图像的显示思路2.图像的采样方法3.图像显示的闪烁问题及其解决办法4.大图像的显示调度算法(GDI环境)5.图像的基本操作原理(漫游、拉框放大、拉框缩小等)6. 图像的插值方法7.OpenGL环境下的图...

emacs基础 csqlwy 博客园

emacs基础 - csqlwy - 博客园 emacs基础 首先几个不错的网站: IBM的emacs编辑环境教程,整个系列教程会由浅入深的向您介绍 Emacs,这个强大的编辑器的各项功能,使您从对它完全不熟悉到能够完成基本操作,以至于最后成为一个高手。 emacs中文网:http://emacser.com/ EmacsWiki:http://www....

提示用户进行版本更新并且发布通知监控版本下载情况

前言: 在我们发布我们的APP之后避免不了升级和加入一些新的功能,一般都是进入软件之后进行检测并且发布通知去下载。当然在更新问题上也要注意用相同的key进行打包。然后优化,好了,下面我们来看它的实现方法 实现效果截图: 首先上一段代码,查看MainActivity的相关处理: import com.jay.verioncheck.VersionC...

家常菜之豆豉蒸鸡翅

从网上搜到的一道家常菜,今天试做了一下。做法如下: 豆豉蒸鸡翅原料:豆豉、鸡翅、生姜、葱、胡椒、辣椒、酱油、盐、食用油适量。制作:1、将鸡翅放在葱、辣椒、酱油、盐中稍腌入味。2、将鸡翅撒上豆豉放入盘中,再放入长姜丝,加入原调味汁和味精,食用油等上笼蒸熟。3、上桌前,加上一点葱花和红辣椒丝。 感觉这样做鸡肉能够入味。...

Boost核心类库精讲

Boost核心类库精讲 Boost核心类库精讲 2011-08-20 14:07 一、课程目标 Boost是由C++标准委员会成员发起、众多C++业界高人参与设计并实现的一个涉及面广、质量高且业已广泛使用的C++标准后备库,其中 TR1已经被纳入C++0x标准库。不论从风格和内容组织上讲,都可以认为Boost项目是C++标准库的延伸。本次课程...