题解：P14076 [GESP202509 六级] 货物运输

· · 题解

前情提要

题目传送门。

想不到本蒟蒻在有生之年能抢上 GESP 的题解。

场上看到 T1 这么难直接绝望，去看 T2，竟然是这么水的 DFS，严重怀疑 CCF 在坑考生。

思路

我们不妨先来考虑如果车队最后必须返回首都，路程应该是多远。

题目明确指出“这 n 座城市由 n-1 条双向道路连接……任意两座城市间均可通过双向道路到达”，说明了这是一个 n 个点， n-1 条边的连通图，学过树论的都知道，这是一棵树。

树有一个特性，两个点之间只有唯一的通路。即，如果你要从 A 点前往 B 点，然后回到 A 点，你必须原路返回。

那么，如果你要走遍所有的点，且走完回到原点，每条边必须走 2 遍，总路程为 2\times (l_1+l_2+\cdots +l_{n-1})，即 2\times\sum_{i=1}^{n-1}l_i。

我们回到原来的问题，车队最后可以不返回首都。

如果车队最后留在 i 号城市，车队本该在从 i 回到 1，因此车队在原来的基础上少走了 1\sim i 这段距离。为了最小化经过的道路长度总和，我们需要找到一个 i，使得 1\sim i 距离最大化。

代码实现

用 DFS 查找每一个节点，用 ans 存储 1\sim i 距离最大值。

#include<bits/stdc++.h>
#define int long long//以防万一开long long
using namespace std;
int n,sum=0,ans=-1e9;//ans初始极小值
int vis[100005];
struct node{
    int v,w;
};
vector<node> e[100005];
void dfs(int x,int val)//x为当前查询节点，val为1到x的距离
{
    //DFS模板
    if(vis[x]) return ;
    vis[x]=1;
    for(node i:e[x]) dfs(i.v,val+i.w);//每次向下搜，val加道路距离
    ans=max(ans,val);//ans取最大值
}
signed main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
        sum+=w;//sum累加总长度
    }
    dfs(1,0);
    cout<<sum*2-ans;//sum别忘*2
    return 0;
}