树的重心求法POJ3107

树的重心POJ3107

题目的意思很明确，就是求所有树的重心（再按字典序输出）。
树是很常见的数据结构，树的重心在树的分治中非常有用，所以对于大规模的树快速求出重心省节时间是一个oi选手需要考虑的问题。
那么我们先介绍一下树的重心。
树的重心定义为：树中的一个点,删掉该点，使剩下的树所构成的森林中最大的子树节点数最少。
树的重心推论：
   1.设树上的一个点S，树上其余所有点到S点的距离之和最小，那么S就是重心。
   2.树的重心不唯一。
   3.以树的重心来做点分治，效率高如POJ1741。
   （见IOI2009中国国家集训队论文 分治算法在树的路径问题中的应用——漆子超）
那么我们依靠定义来求树的重心好了。
首先我们确定一个根，进行一遍dfs，回溯的时候可以递归统计该点不同子树所拥有的点的数量，然后再用（总节点数）减去（1）减去（子树），就是其父亲那边的那棵树的点的数量，区minn，最后求出即可。

***加速加速加速***
1.采用极速输入（见我输入输出的论文）。
2.采取数组存边。
加速效果：

我们看到，TLE是仅采用极速输入，用vector存边的，效果非常差，2000MS的都没A,不说了满脸是泪啊。
然后呢，563MS的是仅采用数组存边，没用极速输入的。
（94MS那个不是这道题滚粗）— —
最后两个优化都用上哈哈哈哈，157MS，该题总排名21（可惜没进第一页）

同志们，我的代码能力很差，大家再参考一下，刷榜不是梦。

附代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<climits>
#include<string>
#include<cstdlib>
#include<set>
#include<stack>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char k=0;char ls;ls=getchar();for(;ls<'0'||ls>'9';k=ls,ls=getchar());
    int x=0;for(;ls>='0'&&ls<='9';ls=getchar())x=x*10+ls-'0';
    if(k=='-')x=0-x;return x;
}

int n;
int k;

int edge[100050];
int zhi[100050];
int zhong[100050];
int g=0;
int sum[100050];
int maxj[100050];
int minn=INT_MAX;

void dfs(int d,int fa)
{
    for(int i=zhong[d];i!=0;i=zhi[i])
    {
        int z=edge[i];
        if(z!=fa)
        {
            dfs(z,d);
        }
    }
    maxj[d]=max(maxj[d],n-sum[d]-1);
    minn=min(minn,maxj[d]);
    sum[d]+=1;
    sum[fa]+=sum[d];
    maxj[fa]=max(sum[d],maxj[fa]);
    return;
}

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read();

    for(int i=1;i<n;++i)
    {
        int a1=read(),b1=read();
        edge[++g]=b1;
        zhi[g]=zhong[a1];
        zhong[a1]=g;

        edge[++g]=a1;
        zhi[g]=zhong[b1];
        zhong[b1]=g;
    }
    dfs(1,0);
    for(int i=1;i<=n;++i)
    if(maxj[i]==minn)
    cout<<i<<" ";
    cout<<endl;
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

最后

以上就是冷艳信封为你收集整理的树的重心求法POJ3107的全部内容，希望文章能够帮你解决树的重心求法POJ3107所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。