題干：

The cows have reconstructed Farmer John's farm, with its N barns (1 <= N <= 150, number 1..N) after the terrible earthquake last May. The cows didn't have time to rebuild any extra roads, so now there is exactly one way to get from any given barn to any other barn. Thus, the farm transportation system can be represented as a tree.?

Farmer John wants to know how much damage another earthquake could do. He wants to know the minimum number of roads whose destruction would isolate a subtree of exactly P (1 <= P <= N) barns from the rest of the barns.

Input

* Line 1: Two integers, N and P?

* Lines 2..N: N-1 lines, each with two integers I and J. Node I is node J's parent in the tree of roads.?

Output

A single line containing the integer that is the minimum number of roads that need to be destroyed for a subtree of P nodes to be isolated.?

Sample Input

11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11

Sample Output

2

Hint

[A subtree with nodes (1, 2, 3, 6, 7, 8) will become isolated if roads 1-4 and 1-5 are destroyed.]?

題目大意：

將一棵n個節點的有根樹，刪掉一些邊變成恰有m個節點的新樹。求最少需要去掉幾條邊。

解題報告：

dp[i][j]代表，以 i 為根節點，砍掉 j 個子節點的子樹，所要刪除的邊的個數

?AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 555; const int INF = 0x3f3f3f3f; int dp[MAX][MAX];//以i節點為根節點，切掉了j個節點的最小刀數 int n,p; vector<int> vv[MAX]; void dfs(int cur,int rt) {int up = vv[cur].size();for(int i = 0; i<up; i++) {int v = vv[cur][i];if(v == rt) continue;dfs(v,cur);for(int j = p; j>1; j--) {for(int k = 1 ; k < j ; ++k)//劃分成子樹下的節點和本身的節點數dp[cur][j] = min(dp[cur][j] , dp[v][k]+dp[cur][j-k]-2);}} } int main() {cin>>n>>p;for(int a,b,i = 1; i<=n-1; i++) {scanf("%d%d",&a,&b);vv[a].pb(b);vv[b].pb(a);}memset(dp,INF,sizeof dp);for(int i = 1; i<=n; i++) dp[i][1] = vv[i].size();dfs(1,-1);int ans = INF;for(int i=1;i<=n;i++) ans=min(dp[i][p],ans);cout <<ans <<endl;return 0 ; }

AC代碼2：

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,p,k,head[160],rd[160],dp[160][160],siz[160],ans=0x3f3f3f; struct edge {int to,next;} ed[330]; void adde(int u,int v){ed[++k].to=v;ed[k].next=head[u];head[u]=k;}void dfs1(int u,int fa) {siz[u]++;for(int i=head[u];i;i=ed[i].next){int v=ed[i].to;if(v==fa) continue;dfs1(v,u);siz[u]+=siz[v];}dp[u][siz[u]]=1;//如果切掉整棵子樹，只需切掉與父節點的連邊 dp[u][0]=0;//不切 }void dfs2(int u,int fa) {for(int i=head[u];i;i=ed[i].next){int v=ed[i].to;if(v==fa) continue;dfs2(v,u);for(int j=siz[u]-1;j;j--)//我切多少 for(int k=0;k<=j;k++)//我的兒子切多少 dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]);//我切j個節點切的最少邊數=min 我切j-k個節點的最少邊數+我的兒子切k個節點的最少邊數 }if(siz[u]-p>=0)//有那么多節點 ans=min(ans,dp[u][siz[u]-p]+dp[u][siz[u]]);//min 切掉siz[u]-p個節點(剩P個節點)的最少邊數+分開我與父親的邊 }int main() {scanf("%d%d",&n,&p);memset(dp,0x3f3f3f,sizeof(dp));//初始化為最大值 for(int i=1;i<=n-1;i++){int u,v;scanf("%d%d",&u,&v);adde(u,v);adde(v,u);}dfs1(1,1);//求siz數組 & 初始化 dp[1][siz[1]]=0;//根節點不需要與父節點分開 （沒有父親。。。） dfs2(1,1);//樹形dp printf("%d",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的【POJ - 1947】Rebuilding Roads （树形dp，背包问题，树形背包dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。