（树的直径）LightOJ -- 1094

链接：

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88230#problem/C

求树的直径，这里只不过给每条边增加一个边长属性，变成了求树上两点距离最远为多少

树的直径，在今天比赛前我是没有接触过的，队友说在学长的博客上看是用了两个bfs就可以了，可我看的题解是用了两个dfs

应该意思是一样的吧！！！都学习一下

题解的代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cstdlib>

using namespace std;

#define N 30005

struct node

{

    int v, next, w;

}edge[N<<];

int Head[N], dis[N];

int cnt, Max, Index;

void Add(int u, int v, int w)

{

    edge[cnt].v = v;

    edge[cnt].w = w;

    edge[cnt].next = Head[u];

    Head[u] = cnt++;

}

void dfs(int u, int w)

{

    dis[u] = w;

    if(dis[u] > Max)

    {

        Max = dis[u];

        Index = u;

    }

    for(int i=Head[u]; i!=-; i=edge[i].next)

    {

        int v = edge[i].v;

        if(dis[v] == -)

            dfs(v, dis[u]+edge[i].w);

    }

}

int main()

{

    int t, n, iCase=;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%d", &n);

        memset(Head, -, sizeof(Head));

        cnt = Max = ;

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

        {

            int u, v, w;

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

            Add(u, v, w);

            Add(v, u, w);

        }

        memset(dis, -, sizeof(dis));

        dfs(, );

        memset(dis, -, sizeof(dis));

        dfs(Index, );

        printf("Case %d: %d\n", iCase++, Max);

    }

    return ;

}

巴特西

（树的直径）LightOJ -- 1094

最新文章

热门文章