#include#include#include#include#include#include#include#include#include" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

1056. Computer Net

系統 1878 0

http://acm.timus.ru/problem.aspx?space=1&num=1056

求樹的圓心

兩遍 bfs 找到直徑 然后圓心有一個或兩個

代碼:

      #include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#include<string>

#include<queue>

#include<stack>

#include <iomanip>

using namespace std;

#define LL long long

const int INF=0x3f3f3f3f;

const int N=10006;

int head[N],I;

struct node

{

    int j,next;

}side[N*2];

int n;

int f[N];

vector<int>road;

void add(int i,int j)

{

    side[I].j=j;

    side[I].next=head[i];

    head[i]=I++;

}

int bfs(int s)

{

    int dist[N];

    memset(dist,-1,sizeof(dist));

    queue<int>qt;

    qt.push(s);

    dist[s]=0;

    int k=s;

    while(!qt.empty())

    {

        int x=qt.front();qt.pop();

        for(int t=head[x];t!=-1;t=side[t].next)

        {

            int j=side[t].j;

            if(dist[j]==-1)

            {

                dist[j]=dist[x]+1;

                f[j]=x;

                if(dist[j]>dist[k])

                k=j;

                qt.push(j);

            }

        }

    }

    road.clear();

    int tmp=k;

    while(tmp!=s)

    {

        road.push_back(tmp);

        tmp=f[tmp];

    }

    road.push_back(s);

    return k;

}

int main()

{

    //freopen("data.in","r",stdin);

    while(cin>>n)

    {

        memset(head,-1,sizeof(head));

        I=0;

        for(int i=2;i<=n;++i)

        {

            int pre;

            cin>>pre;

            add(pre,i);

            add(i,pre);

        }

        bfs(bfs(1));

        int m=road.size();



        if(m&1)

        cout<<road[m/2]<<endl;

        else

        cout<<min(road[m/2],road[m/2]-1)<<" "<<max(road[m/2],road[m/2]-1)<<endl;

    }

    return 0;

}


    

?

1056. Computer Net


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产精欧美一区二区三区 | 欧美黄色录像 | 亚洲人成绝费网站色ww | 真人女人一级毛片免费视频观看 | 国产精品资源在线观看 | 欧美成人私人视频88在线观看 | 亚洲精品国产精品国自产观看 | 搞逼综合网 | 草草在线播放 | 在线免费观看国产精品 | 国产亚洲精品久久久久久牛牛 | 一级特级欧美a毛片免费 | 不卡日本 | 午夜欧美成人 | 色偷偷亚洲第一综合 | 97在线视频免费公开观看 | 天天狠狠色噜噜 | 亚洲成人日韩 | 中文字幕国产综合 | 99久视频| 欧美日韩一区二区综合在线视频 | 免费大片黄在线观看yw | 国产aaa毛片| 色播影音 | 午夜精品福利视频 | 奶交性视频欧美 | 亚洲视频一区在线观看 | 国产一级视频免费 | 亚洲综合日韩中文字幕v在线 | 福利视频久久 | 日韩精品亚洲一级在线观看 | 国产不卡在线观看 | 天天干天天射天天 | 免费看黄片毛片 | 日本免费一区视频 | 神马影院888不卡院 神马影院不卡不卡在线观看 | 日本人的色道www免费一区 | 午夜免费 | 变态捡到女婴h养成调教 | 中国欧美日韩一区二区三区 | 美利坚永久精品视频在线观看 |