题目描述

这里主要分享一下如何用数组来存：
解释我都放在代码中

算法1

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010,M=200010;
int n;
int h[N];//储存表头，即h[a]；
int e[M];//这条边指向谁
int w[M];//这条边的权值
int ne[M];//相当于链表中的next，不过不同的是这里是逆序建表储存的上一条是谁
int idx;
int dist[N];//点x到任意点的距离
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;//逆序建立数组链表
}
void dfs(int u,int father,int distance)//从选中的头出发
{
    dist[u]=distance;
    for(int i=h[u];~i;i=ne[i])//举个例子：第一个i为h[u],那么依据逆序下一个i=ne[h[u]];给定任意一点因为是无向图必然都能找到上一点
    //直到结点为0
    {
        int j=e[i];
        if(j!=father)
        {
            dfs(j,u,distance+w[i]);//以u为父节点，j为子节点向下搜寻
        }
    }
}
int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=0;i<=n-1;i++)
    {
        int a,b,c;
       scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1,0);//父节点设为-1，用以遍历所有可能性
    int u=1;
    for(int i=2;i<=n;i++)
    {
        if(dist[u]<dist[i])
        {
            u=i;
        }
    }
    dfs(u,-1,0);//找到直径端点之后，再找最长
    for(int i=1;i<=n;i++)
    {
        if(dist[u]<dist[i])
        {
            u=i;
        }

    }
     printf("%lld\n", dist[u] * 10 + (dist[u] + 1ll) * dist[u] / 2);
     return 0;

}