首页 > 代码库 > POJ 1947 Rebuilding Roads（树形DP）
POJ 1947 Rebuilding Roads（树形DP）
题目链接
题意 ： 给你一棵树，问你至少断掉几条边能够得到有p个点的子树。
思路 ： dp[i][j]代表的是以i为根的子树有j个节点。dp[u][i] = dp[u][j]+dp[son][i-j]-1,son是u的儿子节点。初始是将所有的儿子都断开，然后-1代表的是这个儿子我需要了，不断了。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #define maxn 101 6 7 using namespace std; 8 9 struct node10 {11 int fa,son,next ;12 } pp[210];13 int head[210],cnt,root[210],root1,dp[210][210] ;14 int p ;15 int so[210];//统计儿子的个数16 void dfs(int u)17 {18 for(int i = 0; i <= p ; i++)19 dp[u][i] = 999999999;20 dp[u][1] = so[u] ;21 for(int ii = head[u] ; ii != -1 ; ii = pp[ii].next)22 {23 int son = pp[ii].son ;24 dfs(son) ;25 for(int i = p ; i >= 0 ; i--)26 {27 int s = dp[u][i] ;28 for(int j = 1 ; j < i ; j++)29 {30 s = min(s,dp[u][j]+dp[son][i-j]-1) ;31 }32 dp[u][i] = s ;33 }34 }35 }36 void addedge(int u,int v)37 {38 pp[cnt].fa = u ;39 pp[cnt].son = v ;40 pp[cnt].next = head[u] ;41 head[u] = cnt ++ ;42 }43 int main()44 {45 int n,u,v;46 while(~scanf("%d %d",&n,&p))47 {48 cnt = 0 ;49 memset(head,-1,sizeof(head)) ;50 memset(root,1,sizeof(root)) ;51 for(int i = 1 ; i < n ; i++)52 {53 scanf("%d %d",&u,&v) ;54 addedge(u,v) ;55 so[u]++;56 root[v] = 0 ;57 }58 for(int i = 1 ; i <= n ; i++)59 if(root[i])60 {61 root1 = i ;//根节点62 break ;63 }64 dfs(root1) ;65 int ans = dp[root1][p] ;66 for(int i = 1 ; i <= n ; i++)67 ans = min(ans,dp[i][p]+1) ;68 printf("%d\n",ans) ;69 }70 return 0;71 }
POJ 1947 Rebuilding Roads（树形DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。