本文主要是介绍poj1947(树形dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：点击打开链接
题意：给出一个n个节点组成的树，问最少删除几条边可以孤立出一个含有m个节点的树
代码：
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int n,p;
int dp[205][205],num[205],used[205]; //dp[i][j]以i为根节点的子树含有j个节点
vector<int> G[205]; //最少需要删除几条边
void dfs1(int s){int i,tmp,sum;sum=0;used[s]=1;for(i=0;i<G[s].size();i++){tmp=G[s][i];if(G[tmp].size()&&!used[tmp]){sum++;dfs1(tmp);num[s]+=num[tmp]; //求出每个节点所含节点个数用于dp}}dp[s][1]=sum; //将每个节点儿子节点全部断开时需要几条边
}
void dfs2(int s){int i,j,k,tmp;used[s]=1;for(i=0;i<G[s].size();i++){tmp=G[s][i];if(G[tmp].size()&&!used[tmp]){dfs2(tmp);for(j=num[s];j>1;j--)for(k=1;k<j;k++)dp[s][j]=min(dp[s][j],dp[s][k]+dp[tmp][j-k]-1);} //因为求出了dp[s][1]，每个状态的开始是有} //dp[s][1]开始的，也就是相当于往上填边的过程}
int main(){int i,j,a,b,ans;while(scanf("%d%d",&n,&p)!=EOF){memset(dp,INF,sizeof(dp));fill(num,num+n+1,1);memset(used,0,sizeof(used));for(i=1;i<=n;i++)G[i].clear();for(i=1;i<n;i++){scanf("%d%d",&a,&b);G[a].push_back(b);G[b].push_back(a);}dfs1(1);memset(used,0,sizeof(used));dfs2(1);ans=dp[1][p];for(i=2;i<=n;i++)ans=min(ans,dp[i][p]+1); //除了根节点其它节点得先与父节点断开printf("%d\n",ans);}return 0;
}
这篇关于poj1947(树形dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
