SP1437 Longest path in a tree（树的直径）

应该是模板题了吧

定义: 树的直径是指一棵树上相距最远的两个点之间的距离。

方法：我使用的是比较常见的方法：两边dfs，第一遍从任意一个节点开始找出最远的节点x，第二遍从x开始做dfs找到最远节点的距离即为树的直径。

证明：假设此树的最长路径是从s到t,我们选择的点为u。反证法：假设第一遍搜到的点是v。

1、v在这条最长路径上，那么dis[u,v]>dis[u,v]+dis[v,s],显然矛盾。

2、v不在这条最长路径上，我们在最长路径上选择一个点为po，则dis[u,v]>dis[u,po]+dis[po,t]，那么有dis[s,v]=dis[s,po]+dis[po,u]+dis[u,v]>dis[s,po]+dis[po,t]=dis[s,t],即dis[s,v]>dis[s,t],矛盾。

也许你想说u本身就在最长路径，或则其它的一些情况，但其实都能用类似于上面的反证法来证明的。

综上所述，你两次dfs(bfs)就可以求出最长路径的两个端点和路径长度。

Coding

#include<bits/stdc++.h>

using namespace std;

const int N = 1e4+5;

int dis[N],n,head[N],cnt;

struct road

{

    int to,next;

}e[N*50];

void add(int x,int y)

{

    e[++cnt].to=y;

    e[cnt].next=head[x];

    head[x]=cnt;

}

void dfs(int x,int step)

{

    if(dis[x]!=0) return ;

    dis[x]=step;

    for(int i=head[x];i;i=e[i].next)

        dfs(e[i].to,step+1);

}

int main()

{

    cin>>n;

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

    {

        int x,y;

        scanf("%d%d",&x,&y);

        add(x,y);

        add(y,x);

    }

    dfs(1,1);

    int Max=0,k;

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

    if(dis[i]>Max) Max=dis[i],k=i;

    memset(dis,0,sizeof(dis));

    dfs(k,1);

    Max=0;

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

    if(dis[i]>Max) Max=dis[i];

    cout<<Max-1;

    return 0;

}

巴特西

SP1437 Longest path in a tree（树的直径）

最新文章

热门文章