本文主要是介绍poj 3107 Godfather(树形DP，点的个数较多, 删点使得剩余部分结点最多的最小值)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、http://poj.org/problem?id=3107
2、题目大意;
有n个点，已知他们之间的关系，连接是双向的，求删除哪个点可以使得剩下的各个部分的点的个数最少
用一个cnt[]数组记录下每个点有多少个子节点
那么我们要求的删除根节点u后剩余部分的最大数就是要么是u的子树中的最大值，要么是除去以u为根的树外的剩余结点数dp[u]=max(max(cnt[v]),n-cnt[u]);
3、AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100005
#define INF 50010
int v[N],tot,next[N],head[N];
int cnt[N];
int dp[N];
int ans,res,n;
void add_edge(int a,int b)
{v[tot]=b;next[tot]=head[a];head[a]=tot++;
}
void dfs(int u,int fa)
{cnt[u]=1;for(int i=head[u]; i!=-1; i=next[i]){int vv=v[i];if(vv!=fa){dfs(vv,u);cnt[u]+=cnt[vv];//计算出以u为根的子树的结点个数ans=max(ans,cnt[vv]);//计算出以子节点为根的最大结点数，这也是去掉父节点u后，下边各部分的最大值}}dp[u]=max(ans,n-cnt[u]);res=min(res,dp[u]);
}
int main()
{int a,b;scanf("%d",&n);tot=0;memset(head,-1,sizeof(head));for(int i=1; i<n; i++){scanf("%d%d",&a,&b);add_edge(a,b);add_edge(b,a);}ans=-INF;res=INF;memset(dp,0,sizeof(dp));dfs(1,0);int flag=0;//printf("%d\n",res);//for(int i=1;i<=n;i++)//printf("&%d\n",dp[i]);for(int i=1;i<=n;i++){if(flag==0 && dp[i]==res){printf("%d",i);flag=1;}else if(flag==1 && dp[i]==res)printf(" %d",i);}printf("\n");return 0;
}
这篇关于poj 3107 Godfather(树形DP，点的个数较多, 删点使得剩余部分结点最多的最小值)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
