洛谷 P1272 重建道路 详解 不懂的看这里

xiaoxiao2021-02-28  30

洛谷 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个节点的子树的道路的最小数目。 输入输出样例 输入样例#1 11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11 输出样例#1 2 说明 【样例解释】 如果道路1-4和1-5被破坏,含有节点(1,2,3,6,7,8)的子树将被分离出来

题目分析

题意应该就不用说了吧,题目中已经讲的很详细了,实在不懂,自己就花花图吧。 本题是一道树形DP,我们令方程dp[i][j]表示为以i为跟节点的子树恰好包括j个节点。 状态转移方程:

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int INF=0x3f3f3f3f; const int N=201; struct arr{ int nd,nx; }bot[N*2]; int du[N],head[N],dp[N][N],vis[N]; int n,k,res=INF,cnt; void add(int u,int v){bot[++cnt].nd=v; bot[cnt].nx=head[u]; head[u]=cnt;} inline int read(){ int x=0,w=1;char ch; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch-48),ch=getchar(); return x*w; } void dfs(int u){ dp[u][1]=du[u];vis[u]=1; for (int i=head[u];i;i=bot[i].nx){ int v=bot[i].nd; if (!vis[v]){ dfs(v); for (int j=k;j>=1;j--) for (int k=1;k<=j;k++) dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-2); /*树形背包类型 这里之所以要减去2,是因为在一开始的时候我们将dp[u][1]初始值赋值为du[u] 这里表示的是只有u这一个节点时,要把所有与它相连的边都切掉 而现在dp[u][j-k]+dp[v][k]都曾将u->v这条边切除过,现在我们要将这条边恢复 将u和v连在一起,这时我们需要将之前多花费两次切除给剪掉 */ } } res=min(res,dp[u][k]); } int main(){ n=read();k=read(); memset(dp,0x3f,sizeof(dp)); for (int i=1;i<n;i++) {int u=read(),v=read();add(u,v); add(v,u);du[u]++;du[v]++;} dfs(1); printf("%d",res); return 0; }

dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-2); 这里之所以要减去2,是因为我们在求dp[u][j-k]和dp[v][k]时, 都曾将u到v这条边切除过一次, 而且是肯定切除过,因为我们定义的dp[u][j]是指的以u为根的子树, 恰好包括j个节点的子树, 而u跟v本来就是父子关系,所以在这儿就是肯定切除的了。 /*这里有两重循环,第一重循环必须是从k到1,第二重可以是1到j或者j到1; 至于第一个为什么是k到1,我们可以按照01背包的想法来理解, 正是因为从1到k时我们会多次调用到dp[u][j],就相当于做完全背包时我们会多次调用之前的值, 就因为可以无限取,而在这里我们只能调用一次,具体我也讲不清楚. 刚刚自己写了下方程,好像会比较容易理解的,我在这里写出来吧. 先来说一下第一个循环k到1的情况: dp[u][5]: min(dp[u][4]+dp[v][1]、dp[u][3]+dp[v][2]、dp[u][2]+dp[v][3]、dp[u][1]+dp[v][4]) dp[u][4]: min(dp[u][3]+dp[v][1]、dp[u][2]+dp[v][2]、dp[u][1]+dp[v][3]) dp[u][3]: min(dp[u][2]+dp[v][1]、dp[u][1]+dp[v][2]) dp[u][2]: min(dp[u][1]+dp[v][1]) 在来看一下第一个循环1到k的情况 dp[u][2]: min(dp[u][1]+dp[v][1]) dp[u][3]: min(dp[u][2]+dp[v][1]、dp[u][1]+dp[v][2]) dp[u][4]: min(dp[u][3]+dp[v][1]、dp[u][2]+dp[v][2]、dp[u][1]+dp[v][3]) dp[u][5]: min(dp[u][4]+dp[v][1]、dp[u][3]+dp[v][2]、dp[u][2]+dp[v][3]、dp[u][1]+dp[v][4]) 是不是发现了这个好对称啊(QWQ),其实我们可以看出,上面那个更新后的dp[u][5] 、dp[u][4]、dp[u][3] 、dp[u][2]都不会在以后的更新中用到;而另一种情况则会用到之前更新的dp[u][3] 、dp[u][2]… 可能会有一个问题,第一种情况不也用到了很多次的dp[u][3] 、dp[u][2],但我们可以看到一旦只要dp[u][3]等被更新后,他在下一次更新中就不会出现了。而我们可以这样理解,这里的一重循环的在更新前所有的dp[u][j]都是一个等级的,比如说现在是等级1,更新一次等级提高一次,并且只能服务于等级比他高的,去更新等级比他高的。所以讲到到这大概能理解吧。(或许是我太蠢了,一个很简单的东西要理解很久QWQ,还请大佬勿喷QWQ)

一个小思考,这道题是不是可以改编一下呢?变成这样子:求恰好切出p个点大小的子树的最小代价。(每条边都有各自的边权) 如果有大佬想出来,可以跟本蒟交流一波QWQ。欢迎评论!

转载请注明原文地址: https://www.6miu.com/read-2250157.html

最新回复(0)