UVA10308 Roads in the North 题解

A_Bit_Cold · 2023-08-06 12:02:27 · 题解

这是一道求树的直径的模板题。

• 利用链式前向星建树。

• 枚举每一个中转节点节点，类似最长路，只是需要求出第一长和第二长的两条路径，记为 Dis_1[i] 和 Dis_2[i]，Dis_1[i]+Dis_2[i] 就为以 i 为中转点的最长路径。

具体见代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
struct Edge{
    int next;
    int to;
    int c;
} edge[N];
int head[N],Dis[N],Dis2[N],sumedge,ans;
void add_edge(int from,int to,int c) {
    sumedge++;
    edge[sumedge].next=head[from];
    edge[sumedge].to=to;
    edge[sumedge].c=c;
    head[from]=sumedge;
    return;
}
//链式前向星
void Diameter_Tree(int node,int father) {//node 初始节点,father 父亲节点
    for(int i=head[node];i;i=edge[i].next) {//遍历 i 所在的每一个节点
        int tmp=edge[i].to;//另一个节点
        if(tmp!=father) {
            Diameter_Tree(tmp,node);
            if(Dis[node]<Dis[tmp]+edge[i].c) {//第一长路径
                Dis2[node]=Dis[node];
                Dis[node]=Dis[tmp]+edge[i].c;
            }
            else if(Dis2[node]<Dis[tmp]+edge[i].c) {//第二长路径
                Dis2[node]=Dis[tmp]+edge[i].c;
            }
        }
    }
    return;
}
int main() {
    int n,u,v,w;
    cin>>n;
    for(int i=1;i<n;i++) {
        cin>>u>>v>>w;
        add_edge(u,v,w),add_edge(v,u,w);//双向加边
    }
    Diameter_Tree(1,0);//求树的直径
    for(int i=1;i<=n;i++) ans=max(ans,Dis[i]+Dis2[i]);//ans 为树的直径
    cout<<ans;
    return 0;
}