ZOJ 3820 Building Fire Stations 求中点+树的直径+BFS

时间：2021-03-27 03:46:25

题意：给一棵树，要求找出两个点，使得所有点到这两个点中距离与自己较近的一个点的距离的最大值（所有点的结果取最大的值，即最远距离）最小。 意思应该都能明白。

解法：考虑将这棵树摆直如下：

ZOJ 3820 Building Fire Stations 求中点+树的直径+BFS

那么我们可以把最中间的那条直径边删掉，然后在分成的两颗子树内求一个直径中心点，那么这两个点就可以作为答案。 反正当时就觉得这样是正确的， 但是不能证明。

于是，几个bfs就可以搞定了。

当时写TLE了，原因是存要删的边我用了map<pair<int,int>,int>， 后来改掉就不T了，map这种东西还是尽量少用。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <string>

#include <vector>

#include <queue>

using namespace std;

#define N 200007

int vis[N],fa[N];

int maxi,maxtag;

struct node

{

    int dis,u;

};

vector<int> G[N];

int U,V;

void bfs(int S)

{

    node now;

    now.u = S;

    now.dis = ;

    maxi = , maxtag = S;

    queue<node> que;

    fa[S] = -;

    memset(vis,,sizeof(vis));

    que.push(now);

    vis[S] = ;

    while(!que.empty())

    {

        node tmp = que.front();

        que.pop();

        int dis = tmp.dis;

        int u = tmp.u;

        if(dis > maxi)    //最远的点

            maxi = dis, maxtag = u;

        for(int i=;i<G[u].size();i++)

        {

            int v = G[u][i];

            if(vis[v]) continue;

            if((u == U && v == V)||(u == V && v == U)) continue;

            now.dis = dis+;

            now.u = v;

            fa[v] = u;

            vis[v] = ;

            que.push(now);

        }

    }

}

int Smaxi,Smaxtag;

int Emaxi,Emaxtag;

void findcenter(int S,int& ma,int& tag)

{

    ma = , tag = S;

    bfs(S);

    int NS = maxtag;

    bfs(NS);

    int NE = maxtag;

    int cnt = (maxi+)/;

    int nc = ;

    int i = NE;

    while()

    {

        nc++;

        if(nc > cnt)

        {

            tag = i;

            break;

        }

        i = fa[i];

    }

    bfs(tag);

    ma = maxi;

}

int main()

{

    int t,n,i,u,v;

    scanf("%d",&t);

    while(t--)

    {

        U = V = -;

        scanf("%d",&n);

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

            G[i].clear();

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

        {

            scanf("%d%d",&u,&v);

            G[u].push_back(v);

            G[v].push_back(u);

        }

        bfs();

        int S = maxtag;

        bfs(S);

        int E = maxtag;

        int cnt = (maxi+)/;

        int nc = ;

        i = E;

        while()

        {

            nc++;

            if(nc >= cnt)

            {

                U = i, V = fa[i];

                break;

            }

            i = fa[i];

        }

        findcenter(S,Smaxi,Smaxtag);

        findcenter(E,Emaxi,Emaxtag);

        printf("%d %d %d\n",max(Smaxi,Emaxi),Smaxtag,Emaxtag);

    }

    return ;

}

相关文章