首页 > 代码库 > poj1655（树形dp）
poj1655（树形dp）
题目链接：http://poj.org/problem?id=1655
题目大意：给一个树，删除其中一个点就会形成一个森林，点的平衡度为删除了这个节点后，所形成多个树，其中组成树的节点最多，节点个数就是那个平衡度。
分析：本题实际求树的重心。树的重心定义为删掉这个节点之后将树分成几部分使得这几部分中点个数的最大值最小。num[i]表示以i点为根节点所含有的节点数。删掉某点后，由各个儿子和父亲为根节点组成的新树，那么dfs处理好每个儿子的数量后，以父亲为根节点的树的节点数为n-num[i]。这几部分中取最大值即可。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 20010#define clr(a) (memset(a,0,sizeof(a)))using namespace std;struct edge{ int next,v; edge(){} edge(int v,int next):v(v),next(next){}}e[N*2];int dp[N],head[N],num[N],tot,n;void addedge(int u,int v){ e[tot]=edge(v,head[u]); head[u]=tot++;}void dfs(int u,int fa){ int mx=0; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(v==fa)continue; dfs(v,u); num[u]+=num[v]; mx=max(num[v],mx); } dp[u]=max(mx,n-num[u]);}int main(){ int u,v,t; scanf("%d",&t); while(t--) { tot=0;clr(dp); memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=1;i<=n;i++)num[i]=1; for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs(1,0); int ans=inf,id; for(int i=1;i<=n;i++) { if(dp[i]<ans)ans=dp[i],id=i; } printf("%d %d\n",id,ans); }}
poj1655（树形dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。