SGU_134Centroid解题报告求树的重心 spectral centroid

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);
SGU_134Centroid解题报告(求树的重心) spectral centroid
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;
}

  

爱华网本文地址 » http://www.aihuau.com/a/25101013/179765.html

更多阅读

发财树的养殖方法和注意事项 发财树摆放禁忌

发财树的养殖方法和注意事项——简介发财树的养殖方法和注意事项,特点:耐阴,耐旱要诀:防湿,防冻发财树的养殖方法和注意事项——工具/原料盆土水肥料发财树的养殖方法和注意事项——方法/步骤发财树的养殖方法和注意事项 1、一、环境的

金钱树的养殖方法 金钱树叶子发黄怎么办

最近2至3年,有一种被称作金钱树的观叶植物,从南到北闪亮登场,售价不菲,每株价格高达数百元,且销路颇好。它于1997年从荷兰引进在广州芳村和顺德 陈村露面,1999年昆明世博会上,人们还不清楚其姓啥名甚,仅以其外部形态特征将其称作“金钱树”

香樟树的外形特征和作用 香樟树春夏秋冬的特点

香樟树的外形特征和作用——简介香樟树是常绿乔木,一年四季都是绿色而且有香气。香樟树的全身都是宝,从树叶到树根,都可以入药,而且还是非常优良的木材。下面winterpoem就给大家介绍一下香樟树的外形特征及其作用。香樟树的外形特征和

幸福树的正确养殖方法 幸福树的扦插养殖方法

幸福树的正确养殖方法——简介 幸福树因为他有寓意的名称深受家庭、办公环境的喜爱,尤其是它枝繁叶茂,树叶小而翠绿,极具观赏性,无论是放在室内室外都吸引人的注目,展示着旺盛的生命力而且还能净化空气。幸福树又称菜豆树,发源地中国南部

声明:《SGU_134Centroid解题报告求树的重心 spectral centroid》为网友给力侽刄分享!如侵犯到您的合法权益请联系我们删除