爱华网134.Centroid
time limit pertest: 0.50 sec.
memory limit per test: 4096 KB
You are given an undirected connected graph, withN vertices and N-1 edges (a tree). You must find thecentroid(s) of the tree.
In order to define the centroid, some integer value will beassosciated to every vertex. Let's consider the vertex k. Ifwe remove the vertex k from the tree (along with itsadjacent edges), the remaining graph will have only N-1vertices and may be composed of more than one connected components.Each of these components is (obviously) a tree. The valueassociated to vertex k is the largest number of verticescontained by some connected component in the remaining graph, afterthe removal of vertex k. All the vertices for which theassociated value is minimum are consideredcentroids.
Input
The first line of the input contains the integernumber N (1<=N<=16000). The next N-1 lines will contain two integers,a and b, separated by blanks, meaning that thereexists an edge between vertex a and vertexb.
Output
You should print two lines. The first line shouldcontain the minimum value associated to the centroid(s) and thenumber of centroids. The second line should contain the list ofvertices which are centroids, sorted in ascendingorder.
Sample Input
7
1 2
2 3
2 4
1 5
5 6
6 7
Sample Output
3 1
1
--------------------------------------翻译-----------------------------------------------------
重心
时间限制: 0.50sec
空间限制: 4096KB
给你一个连通的无向图，他有N 个顶点和N-1 条边 (一棵树)。现在你需要找到这棵树的重心。现在定义树的重心，树的每一个顶点有一个权值。考虑顶点k。如果从图中删除k号顶点(连带的边也一起被删除)，剩下的图将只有N-1 个顶点而且可能由多个连通分量组成。显然每一个连通分量还是一棵树。那么k号顶点的权值就是删除它以后剩下的连通分量中顶点数最多的顶点个数，删除k之后。这N 个顶点中权值最小的就是重心。
输入
第一行是整数N(1<=N<=16 000)。接下来 N-1 行每行两个整数，a 和 b，用空格隔开，表示顶点a 和 顶点 b之间有一条边。
输出
第一行输出两个整数，最小的权值和重心的个数，第二行按递增顺序输出这些重心的编号。数据之间用一个空格隔开。
样例输入
71 22 32 4155 66 7
样例输出
31
1
---------------------------------------分析-------------------------------------------------------
此题要求我们求一棵树的重心。
给定一棵N个结点的树，求该树的所有重心。重心的定义如下：
删掉某结点i后，若剩余k个连通分量，那么定义d(i)为这些连通分量中结点数的最大值。
所谓重心，就是使得d(i)最小的结点i。
算法分析：建立边表data。由于是无向的，因此边表长度为(N - 1) * 2。边表按照p1端点递增的顺序排序，以便计算每一个顶点的边表序号
树的基本操作:以结点1为根，计算出每个结点所在的子树的结点数。
枚举每一个结点，若将其删掉，那么考虑剩余的所有连通分量。
1、它的子树，其结点数可以直接调用。
2、它的上方子树，其结点数可通过n-1-减去所有子树的结点数算出。
这样，在其中选择d(i)最小的即可。时间复杂度：O(N)，空间复杂度：O(N)
#include<cstdio>#include<climits>
#include<iostream>
usingnamespacestd;
intm,n,Count,List[16001],Ans=INT_MAX,E,Son1[32001],Pre1[32001],Last1[32001],Pre[32001],Last[16001],Son[32001],Child[16001];
voidInit()
{
inti,x,y;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&n);
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
m++;
Son1[m]=y;
Pre1[m]=Last1[x];
Last1[x]=m;
m++;
Son1[m]=x;
Pre1[m]=Last1[y];
Last1[y]=m;
//边表存储
}
}
intDfs(introot,intv)//Dfs把无向图化为有向图
{
intp,now;
if(Last1[root]==0)
{
Child[root]=1;
return1;
}
p=Last1[root];
now=0;
while(p>0)
{
if(Son1[p]!=v)
{
E++;
Son[E]=Son1[p];
Pre[E]=Last[root];
Last[root]=E;
now+=Dfs(Son1[p],root);
}
p=Pre1[p];
}
Child[root]=now+1;
returnnow+1;
}
voidSlove()
{
inti,p,now;
Child[1]=Dfs(1,0);
for(i=1;i<=n;i++)//枚举删除哪个节点
{
p=Last[i];
now=0;
while(p>0)
{
now=max(now,Child[Son[p]]);
p=Pre[p];
}
now=max(now,n-Child[i]);
if(now<Ans)
{
Count=1;
Ans=now;
List[1]=i;
}
elseif(now==Ans)
List[++Count]=i;
}
}
voidPrint()
{
printf("%d%dn",Ans,Count);
for(inti=1;i<Count;i++)
printf("%d",List[i]);
printf("%dn",List[Count]);
fclose(stdin);
fclose(stdout);
}
intmain()
{
Init();
Slove();
Print();
return0;
}
