题意
求树的重心。
思路
树的重心的定义是：选树中某个点i当作树的根，所有子树中最大的那棵的大小是Si，整棵树中能令Si最小的那个点，就是树的重心。
求重心是作为树分治的一个环节出现的，只有保证了每一次点分治的位置都是重心才能保证树分治的复杂度为O(nlogn)。
求重心的想法是树dp，对于每个节点都要存储他所有孩子对应的子树中最大子树的大小，还要存储他的父亲是谁。求好了这些数据之后，按着定义，就可以知道谁是重心了。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; const int MAXV = 20005; const int MAXE = 40005; struct Graph{ int siz[MAXV]; int dp[MAXV]; int par[MAXV]; int head[MAXV]; int nxt[MAXE]; int end[MAXE]; int tot; void init(){ memset(head,0,sizeof(head)); tot = 2; } void addEdge(int from,int to){ end[tot] = to; nxt[tot] = head[from]; head[from] = tot++; } } gph; int n; void dfs(int cur,int par){ gph.par[cur] = par; gph.siz[cur] = 1; gph.dp[cur] = 1; for(int j = gph.head[cur]; j; j = gph.nxt[j]){ int now = gph.end[j]; if(now != par){ dfs(now,cur); gph.siz[cur] += gph.siz[now]; gph.dp[cur] = max(gph.siz[now],gph.dp[cur]); } } } int balance(int &mib){ dfs(1,0); int ret = 0; mib = 0x3f3f3f3f; for(int i = 1; i <= n; i++){ int dpn = max(gph.dp[i],n-gph.siz[i]); if(dpn < mib){ mib = dpn; ret = i; } } return ret; } int main(){ int caseCnt; scanf(" %d",&caseCnt); for(int d = 1; d <= caseCnt; d++){ scanf(" %d",&n); gph.init(); for(int i = 1; i < n ; i++){ int a,b; scanf(" %d %d",&a,&b); gph.addEdge(a,b); gph.addEdge(b,a); } int mib; int res = balance(mib); printf("%d %d\n",res,mib); } return 0; } |
December 06, 2015
[…] 和这个题一致 […]
December 06, 2015
[…] 请参考这个题和／或这个题 […]
January 22, 2016
[…] POJ 1655 Balancing Act：求树的重心 […]