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

2020-02-14 16:01:25来源:博客园 阅读 ()

容器云强势上线!快速搭建集群,上万Linux镜像随意使用

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

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

样例输入:

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
如有疑问请与原作者联系

标签:POSTemClass定义iOS记录

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

上一篇:【做题笔记】[NOIOJ,非NOIp原题]装箱问题

下一篇:Qt5 error LNK2019 无法解析的外部符号的解决办法