题解：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

距离最大值。

CPP

#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;
}

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

文章操作

前情提要

思路

代码实现

相关推荐

评论

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