Balancing Act http://poj.org/problem?id=1655
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 17497 | Accepted: 7398 |
- Description
- Consider a tree T with N (1 <= N <= 20,000) nodes numbered 1...N. Deleting any node from the tree yields a forest: a collection of one or more trees. Define the balance of a node to be the size of the largest tree in the forest T created by deleting that node from T.
- For example, consider the tree:
- Deleting node 4 yields two trees whose member nodes are {
- 5
- } and {
- 1,2,3,6,7
- }. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {
- 2,6
- }, {
- 3,7
- }, and {
- 4,5
- }. Each of these trees has two nodes, so the balance of node 1 is two.
- For each input tree, calculate the node that has the minimum balance. If multiple nodes have equal balance, output the one with the lowest number.
- Input
The first line of input contains a single integer t (1 <= t <= 20), the number of test cases. The first line of each test case contains an integer N (1 <= N <= 20,000), the number of congruence. The next N-1 lines each contains two space-separated node numbers that are the endpoints of an edge in the tree. No edge will be listed twice, and all edges will be listed.
- Output
- For each test case, print a line containing two integers, the number of the node with minimum balance and the balance of that node.
- Sample Input
- 1
- 7
- 2 6
- 1 2
- 1 4
- 4 5
- 3 7
- 3 1
- Sample Output
- 1 2
- Source
- POJ Monthly--2004.05.15 IOI 2003 sample task
题意就是找树的重心, 然后通过树的重心的概念, 找到树的重心, 删掉之后子树是最平衡的. 直接贴的模板.
代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<bitset>
- #include<cassert>
- #include<cctype>
- #include<cmath>
- #include<cstdlib>
- #include<ctime>
- #include<deque>
- #include<iomanip>
- #include<list>
- #include<map>
- #include<queue>
- #include<set>
- #include<stack>
- #include<vector>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int,int> pii;
- const double PI=acos(-1.0);
- const double eps=1e-6;
- const ll mod=1e9+7;
- const int inf=0x3f3f3f3f;
- const int maxn=1e5+10;
- const int maxm=100+10;
- #define iOS iOS::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- int n,father;
- int siz[maxn];//siz 保存每个节点的子树大小
- bool vist[maxn];
- int point=inf,minsum=-1;//minsum 表示切掉重心后最大连通块的大小
- vector<int>G[maxn];
- void DFS(int u,int x)// 遍历到节点 x,x 的父亲是 u
- {
- siz[x]=1;
- bool flag=true;
- for(int i=0;i<G[x].size();i++){
- int v=G[x][i];
- if(!vist[v]){
- vist[v]=true;
- DFS(x,v);// 访问子节点.
- siz[x]+=siz[v];// 回溯计算本节点的 siz
- if(siz[v]>n/2) flag=false;// 判断节点 x 是不是重心.
- }
- }
- if(n-siz[x]>n/2) flag=false;// 判断节点 x 是不是重心.
- if(flag&&x<point) point=x,father=u;// 这里写 x<point 是因为本题中要求节点编号最小的重心.
- }
- void init()
- {
- memset(vist,false,sizeof(vist));
- memset(siz,0,sizeof(siz));
- minsum=-1;
- point=inf;
- for(int i=0;i<maxn;i++) G[i].clear();
- }
- int main()
- {
- int t;
- scanf("%d",&t);
- while(t--){
- scanf("%d",&n);
- init();
- for(int i=1;i<n;i++){
- int u,v;
- scanf("%d%d",&u,&v);
- G[u].push_back(v);
- G[v].push_back(u);
- }
- vist[1]=1;
- DFS(-1,1);// 任意选取节点作为根, 根节点的父亲是 - 1.
- for(int i=0;i<G[point].size();i++)
- if(G[point][i]==father) minsum=max(minsum,n-siz[point]);
- else minsum=max(minsum,siz[G[point][i]]);
- printf("%d %d\n",point,minsum);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2930265.html