一開始狀態(tài)定義錯(cuò)了……所以沒有對(duì)qwq，以及有幾個(gè)坑qwq……

　　首先 f [ i ] [ j ] 表示以 i 為根的子樹，切除 j 個(gè)節(jié)點(diǎn)所需要切除的最小邊數(shù)，而我一開始定義的是表示以 i 為根的子樹，切除后生成一顆有 j 個(gè)節(jié)點(diǎn)的子樹，所需要切除的最小邊數(shù)。

　　為什么我的不行吶？因?yàn)閷?duì)于一個(gè)新的子節(jié)點(diǎn)更新狀態(tài)，它能生成多大的子樹其實(shí)是和父親節(jié)點(diǎn)是沒有關(guān)系的，即它與父親節(jié)點(diǎn)原來的狀態(tài)無關(guān)也，兩棵樹不也連通，然而對(duì)于切除多少點(diǎn)，我們?cè)谝獾氖乔谐笫５?#xff0c;而不是切除的。那么最后的ans就是 f [ ... ]?[ num - p ] + f [?... ] [?num [ ...?] ]了。?

　　以及，根節(jié)點(diǎn)的?f [ ] num是0，因?yàn)樗鼪]有父親節(jié)點(diǎn)本身就是一顆含有 num 個(gè)點(diǎn)的（子）樹。

　　代碼如下：

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; #define maxn 2000 struct node {int to,nxt; } edge[maxn]; int f[maxn][maxn],num[maxn],head[maxn]; int n,p,cnt,ans=999999999; void add(int a,int b) {edge[++cnt].to=b;edge[cnt].nxt=head[a];head[a]=cnt; } void dfs(int u,int fa) {num[u]=1;for(int i=head[u]; i; i=edge[i].nxt){int tot=0,am=0;int v=edge[i].to;if(v==fa) continue;dfs(v,u);num[u]+=num[v];f[u][num[v]]=1;am+=num[v];f[u][am]=++tot;}f[u][num[u]]=1;f[u][0]=0;if(u==1) f[u][num[u]]=0; } void dp(int u,int fa) {for(int i=head[u]; i; i=edge[i].nxt){int v=edge[i].to;if(v==fa) continue;dp(v,u);for(int j=num[u]; j>=0; j--)for(int k=0; k<=j; k++)f[u][j]=min(f[u][j],f[u][j-k]+f[v][k]);}if(num[u]>=p)ans=min(ans,f[u][num[u]-p]+f[u][num[u]]); } int main() {memset(f,0x3f3f3f3f,sizeof(f));scanf("%d%d",&n,&p);for(int i=1; i<n; i++){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}dfs(1,0);dp(1,0);printf("%d",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/popo-black-cat/p/10337025.html

總結(jié)

以上是生活随笔為你收集整理的P1272 重建道路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。