題目描述

一場可怕的地震后，人們用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

思路：樹形dp

使用?vector<int> g[N]，用 g[i] 來保存所有結點，用 f[i][j] 來代表結點 i 保留 j 個結點最少需要刪去的邊的個數，則有狀態轉移：f[x][j]=min(f[x][j],f[x][j-k]+f[y][k]-1)，其中 y?是 x?的子結點

源代碼

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<ctime> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 10007 #define E 1e-6 #define LL long long using namespace std; vector<int> g[N]; int son[N],sum[N]; int f[N][N]; void treeDP(int x){sum[x]=1;int num=g[x].size();//兒子的個數if(!num){f[x][1]=0;sum[x]=1;return;}for(int i=0;i<num;i++){//枚舉每個兒子int y=g[x][i];treeDP(y);sum[x]+=sum[y];for(int j=sum[x];j>=0;j--)for(int k=1;k<j;k++)f[x][j]=min(f[x][j],f[x][j-k]+f[y][k]-1);} } int main() {int n,p;cin>>n>>p;for(int i=1;i<n;i++){int x,y;cin>>x>>y;g[x].push_back(y);son[x]++;//記錄兒子個數}memset(f,INF,sizeof(f));for(int i=1;i<n;i++)//只剩一個結點時，所有的兒子都減掉f[i][1]=son[i];treeDP(1);int res=f[1][p];for(int i=2;i<=n;i++)res=min(res,f[i][p]+1);cout<<res<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的重建道路（洛谷-P1272）的全部內容，希望文章能夠幫你解決所遇到的問題。

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