<題目鏈接>

題目大意：
給你一棵樹，任意去除某一個點后，樹被分成了幾個聯通塊，則該點的平衡值為所有分成的連通塊中，點數最大的那個，問你：該樹所有點中，平衡值最小的那個點是什么？

解題分析：

運用DFS，找到以u為根節點，所有子節點數的最大值，然后求出這些最大值的最小值。

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int MAXN = 2e4+7; 7 struct Edge{ 8 int to,next; 9 }edge[MAXN*2]; //注意這里要*2，因為要存雙向邊 10 11 int head[MAXN],tot; 12 void init(){ 13 memset(head,-1,sizeof(head)); 14 tot = 0; 15 } 16 void addedge(int u,int v){ 17 edge[tot].to = v;edge[tot].next = head[u]; 18 head[u] = tot++; 19 } 20 int dp[MAXN],num[MAXN]; 21 int n; 22 23 void dfs(int u,int pre){ 24 dp[u] = 0;num[u] = 1; 25 for(int i = head[u];i != -1;i = edge[i].next){ 26 int v = edge[i].to; 27 if(v == pre)continue; //如果下一個點是u的父親(即剛剛走過的點)，那么跳過，防止下一步dfs(v,u)遍歷該無向圖時,不停的在兩個點之間來回遍歷 28 dfs(v,u); //繼續從它的子節點開始向下搜索 29 dp[u] = max(dp[u],num[v]); //dp[u]指的是u的每個子節點方向所對應的最大節點數的最大值 30 num[u] += num[v]; 31 } 32 //num[u]此時代表除父節點方向外的所有子節點數(包括它本身,，因為num[u]初始化為1) 33 dp[u] = max(dp[u],n - num[u]); //n-num[u]指的是dp[u]父節點方向的節點數 34 } 35 36 int main(){ 37 int T;scanf("%d",&T); 38 int u,v; 39 while(T--){ 40 scanf("%d",&n); 41 init(); 42 for(int i = 1;i < n;i++){ 43 scanf("%d%d",&u,&v); 44 addedge(u,v);addedge(v,u); 45 } 46 dfs(1,-1); 47 int loc=-1,ans=1e9; 48 for(int i=1;i<=n;i++){ 49 if(ans>dp[i]) 50 ans=dp[i],loc=i; 51 } 52 printf("%d %d\n",loc,ans); 53 } 54 return 0; 55 }

?

?

?

2018-08-17

轉載于:https://www.cnblogs.com/00isok/p/9491817.html

總結

以上是生活随笔為你收集整理的POJ 1655 Balancing Act (求树的重心)【树形DP】(经典)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。