本文主要是介绍poj 1655 Balancing Act(树形DP，删点)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、http://poj.org/problem?id=1655
2、题目大意：
一棵树有n个点，每个点都有一个平衡值，就是该点的子树中结点数最大值，现在要删除这样一个点，他的平衡值最小，本题只有一种方式，不用考虑是否有重复值，只需要输出最小的那个点及他的平衡值即可
dp[i]表示i点的平衡值
dp[i]=max(max(cnt[v]),n-cnt[u])
3、AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 20005
#define INF 20005
int v[N*2],next[N*2],head[N*2];
int tot;
int cnt[N];
int ans,res,n;
int dp[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];ans=max(ans,cnt[vv]);}}dp[u]=max(ans,n-cnt[u]);res=min(dp[u],res);
}
int main()
{int t,a,b;scanf("%d",&t);while(t--){scanf("%d",&n);tot=0;memset(head,-1,sizeof(head));memset(cnt,0,sizeof(cnt));memset(dp,0,sizeof(dp));for(int i=1;i<n;i++){scanf("%d%d",&a,&b);add_edge(a,b);add_edge(b,a);}ans=-INF;res=INF;dfs(1,0);for(int i=1;i<=n;i++){if(dp[i]==res){printf("%d %d\n",i,dp[i]);break;}}}return 0;
}/*
8
2 6
1 2
1 4
4 5
3 7
3 1
1 8
*/
这篇关于poj 1655 Balancing Act(树形DP，删点)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
