【学习笔记】[图论]树的直径

非严格定义：在一棵带权树上，相聚距离最大的两个点或最长链的长度，称之为树的直径

样例输入：

4
1 2 10
1 3 12
1 4 15

样例输出

27

似乎并没有什么难理解的地方。

解法1：DP

咕着

解法2：DFS

经过思考，发现一个重要的性质：离树上的某一结点最远的那个结点，定是直径的一个端点。

那么就好办了！找到任一点的最远点，再找到这个最远点的远点，这条路径就是树的直径。所以需要两次 DFS 。

#include <iostream>
#include <cstdio>
#include <cstring>

const int N=1000010;

using namespace std;

int n,m,head[N],tot,dis[N],cur,mx;
//mx是最远距离

struct Edge
{
    int to,next,val;
};
Edge G[N<<1];

inline int read()
{
    int w=1,s=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}

inline void addedge(int u,int v,int w)
{
    G[++tot]=(Edge){v,head[u],w},head[u]=tot;
    G[++tot]=(Edge){u,head[v],w},head[v]=tot;
}

inline void dfs(int u,int fa)
{
    for(int i=head[u];i;i=G[i].next)
    {
        int v=G[i].to;if(v==fa)continue;
        dis[v]=dis[u]+G[i].val;
        if(dis[v]>mx)cur=v,mx=dis[v];
        dfs(v,u);
    }
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read(),w=read();
        addedge(u,v,w);
    }
    dfs(1,0);mx=0;memset(dis,0,sizeof(dis));
    //清空上一次 dfs 记录的状态
    dfs(cur,0); //从上一次找到的端点开始再次寻找
    cout<<mx<<endl;
    return 0;
}

原文链接:https://www.cnblogs.com/Nicest1919/p/12309274.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有