POJ 2631 Roads in the North(树的直径)

http://poj.org/problem?

id=2631

题意:

有一个树结构, 给你树的全部边(u,v,cost), 表示u和v两点间有一条距离为cost的边. 然后问你该树上最远的两个点的距离是多少?(即树的直径)

分析:

对于树的直径问题, <<算法导论>>(22 2-7)例题有说明.

详细解法: 首先从树上随意一个点a出发, (BFS)找出到这个点距离最远的点b. 然后在从b点出发(BFS)找到距离b点最远的点c. 那么bc间的距离就是树的直径.

程序实现用的是邻接表来表示树结构.

Head[i]==j 表示与i结点连接的边组成了一条链表, 当中第j条边是这条链的头一个元素, 接着通过j能够找到剩余的(与i连接的)边.

Edge是用来表示每条边的结构.

BFS返回从s结点能走到的最远的点的编号

AC代码: C++提交才行

//C++提交才行

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn=10000+5;

const int maxm=1000000+5;

//边结构

struct Edge

{

    Edge(){}

    Edge(int to,int cost,int next):to(to),cost(cost),next(next){}

    int to;

    int cost;

    int next;

}edges[maxm];  //全部边

int cnt;       //边总数

int head[maxn];//头结点

//加入两条有向边

void AddEdge(int u,int v,int cost)

{

    edges[cnt]=Edge(v,cost,head[u]);

    head[u]=cnt++;

    edges[cnt]=Edge(u,cost,head[v]);

    head[v]=cnt++;

}

//dist[i]表当前点到i的距离

int dist[maxn];

//BFS返回从s结点能走到的最远的点的编号

int BFS(int s)

{

    int max_dist=0;//记录最远距离

    int id=s;      //记录最远点

    queue<int> Q;

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

    dist[s]=0;

    Q.push(s);

    while(!Q.empty())

    {

        int u=Q.front(); Q.pop();

        if(dist[u]>max_dist)

        {

            max_dist=dist[u];

            id=u;

        }

        for(int i=head[u];i!=-1;i=edges[i].next)

        {

            Edge &e=edges[i];

            if(dist[e.to]==-1)//未訪问过e.to点

            {

                dist[e.to]=dist[u]+e.cost;

                Q.push(e.to);

            }

        }

    }

    return id;

}

int main()

{

    int u,v,cost;

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

    cnt=0;

    while(scanf("%d%d%d",&u,&v,&cost)==3)

        AddEdge(u,v,cost);

    printf("%d\n",dist[BFS(BFS(u))]);

    return 0;

}