首页 > 代码库 > poj1947 Rebuilding Roads
poj1947 Rebuilding Roads
Rebuilding Roads
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 9105 | Accepted: 4122 |
Description
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.
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.
* 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 61 21 31 41 52 62 72 84 94 104 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.]
题意:最小多少切割次数切割出一棵P节点的子树
思路:不要以为是切掉P个点...是切出
1 dp[i][j]节点i切成j的子树所需要的最小切数
2 有两种转移,第一种切断子树,需要+1,第二种合并子树
具体看代码,注意不要互相更新
错误5次:1 胡乱提交 2 互相更新 3 忘了非根子树要切
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=152;const int inf=0x7ffff;int dp[maxn][maxn];int des[maxn];//中间缓存防止自身更新int e[maxn][maxn];int len[maxn];//建图int lef[maxn];//子节点+自身个数int n,p;void dfs(int s){ lef[s]=1;//自身肯定算一个,子节点还没加上 dp[s][1]=0;//这个时候只有不切一种可能 if(len[s]==0){return ;}//没必要刻意 for(int i=0;i<len[s];i++){ int t=e[s][i]; dfs(t); fill(des,des+n+1,inf);//初始化缓存 for(int k=1;k<=lef[s];k++){ des[k]=dp[s][k]+1;//切 } for(int k=1;k<=lef[s];k++){ for(int j=1;j<=lef[t];j++){ des[k+j]=min(dp[s][k]+dp[t][j],des[k+j]);//不切 } } lef[s]+=lef[t];//加上这一枝 for(int k=1;k<=lef[s];k++){ dp[s][k]=des[k];//从缓存中取状态 } dp[s][lef[s]]=0;//不需要 }}int main(){ scanf("%d%d",&n,&p); memset(len,0,sizeof(len)); for(int i=1;i<=n;i++)fill(dp[i]+1,dp[i]+n+1,inf); for(int i=2;i<=n;i++){ int f,t; scanf("%d%d",&f,&t); e[f][len[f]++]=t; } dfs(1); int ans=dp[1][p];//1是根节点分离它不需要切 for(int i=2;i<=n;i++)ans=min(ans,dp[i][p]+1);//非根子树都要切 // printdp(); printf("%d\n",ans); return 0;}
poj1947 Rebuilding Roads
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。