洛谷 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\n",ans);
return 0;
}

2018.5.6

上一篇:Servlet程序开发--Servlet 与 表单


下一篇:洛谷 P4097 [HEOI2013]Segment 解题报告