首页 > 代码库 > SGU 134.Centroid（图心）

SGU 134.Centroid（图心）

2024-07-11 08:14:50   212人阅读

SGU链接：

时间限制：0.25s

空间限制：4M

题意：

      给出一个树（节点数<=16000），一个节点的重量定义为从树中去除这个点后，新得到的所有树中节点最多的树的节点数。树的中心定义为所有节点重量最小的那几个。

      要求输出给定树的树的中心的重量，以及所有的树心的编号。

 

 

 

 

 

Solution：

             首先，以任意节点为根，构造一颗具有父子节点关系的树。

             使用递归即可，Fa[i]记录i的父亲节点编号。

             sum[i],记录i节点以其所有儿子节点一共有多少个节点。 

             显然如果以1号节点为根 sum[1]=n;

             再来考虑如何得到一个节点的重量。

             对于根节点，它的重量是 所有 儿子节点sum[j]中的最大值。

             对于根节点的儿子k呢？

             它的重量是他的 所有儿子节点的sum[]和 (sum[1]-sum[k])的最大值。

             那么对于k的儿子呢？

             这时可以注意到计算k 的时候与根节点其他儿子已经没有关系了，需要的只是sum[i],

             在计算k儿子时，把k当做根，这时sum[k]=n;

             设p为k的儿子,

             p的重量就是 它所有儿子的sum[]和 (sum[k]-sum[p])的最大值.

             最后只要存下不同重量的节点有哪一些输出就可以了。

参考代码：

 

#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <queue>#include <vector>#define INF 16666using namespace std;struct node {	int v, ne;} edge[INF<<2];queue<int> ql;int head[INF], fa[INF], pd[INF];int sum[INF], cnt, nCnt[INF];vector<int>  out[INF];int n, m, ans = INF;void added (int u, int v) {	edge[++cnt].v = v;	edge[cnt].ne = head[u];head[u] = cnt;}int Count (int x) {	pd[x] = sum[x] = 1;	for (int i = head[x]; i != 0; i = edge[i].ne) {		int j = edge[i].v;		if (!pd[j]) {			fa[j] = x;			sum[x] += Count (j);		}	}	return sum[x];}void make (int x) {	int k=0;	if (fa[x] != 0) k = sum[fa[x]] - sum[x];	for (int i = head[x]; i != 0; i = edge[i].ne) {		int j = edge[i].v;		if (j != fa[x]){			k = max (k, sum[j]);			if(fa[x]!=0) sum[x]=sum[fa[x]];			make(j);		}	}	if (ans >= k) {		ans = k;		out[k].push_back (x);		nCnt[k]++;	}}int main() {	int x, y, c;	scanf ("%d", &n);	for (int i = 1; i <= n - 1; i++) {		scanf ("%d %d", &x, &y);		added (x, y), added (y, x);	}	Count (1);	make (1);	printf ("%d %d\n", ans, nCnt[ans]);	sort (out[ans].begin(), out[ans].end() );	for (int i = 0; i <= out[ans].size() - 1; i++)		printf ("%d ", out[ans][i]);	return 0;}

 

　　

 


联系
我们