记录131#includebits/stdc.h using namespace std; #define ll long long//定义长整型别名ll因为边权和最大可达1e14必须用long long const int N1e510;//定义常量N表示城市数量的最大范围 vectorpairint,llg[N];//定义邻接表gg[u]存储与城市u相连的{相邻城市, 道路长度} ll max_dist0;//定义变量max_dist用来记录首都到最远城市的距离 //定义深度优先搜索函数u是当前城市fa是父节点防止走回头路d是当前走过的距离 void dfs(int u,int fa,ll d){ max_distmax(max_dist,d);//每次到达一个节点都尝试更新最远距离 for(auto edge:g[u]){//遍历当前城市u的所有相邻道路 int vedge.first;//相邻的城市编号 ll wedge.second;//这条道路的长度 if(v!fa){//如果相邻城市不是父节点即不是回头路 dfs(v,u,dw);//继续向下深搜距离累加当前道路长度 } } } int main(){//主函数入口 ios::sync_with_stdio(false);//关闭标准流同步提升输入输出效率 cin.tie(0);//解除cin与cout的绑定进一步加快读取速度 int n;//变量n表示城市的总数 ll sum0;//定义变量sum用来累加所有道路的长度总和 cinn;//读入城市的数量n for(int i1;in;i){//循环读入n-1条道路的信息 int u,v;//定义临时变量u和v代表一条道路连接的两个城市 ll len;//定义临时变量len代表这条道路的长度 cinuvlen;//读入这条道路连接的两个城市编号以及长度 g[u].push_back({v,len});//在邻接表中添加u到v的连接 g[v].push_back({u,len});//在邻接表中添加v到u的连接因为是无向图 sumlen;//累加所有道路的长度 } dfs(1,0,0);//从首都1号城市开始进行DFS父节点设为0初始距离为0 cout2*sum-max_dist;//输出最短总路程所有边走两倍的代价减去最远的一条回程 return 0;//程序结束 }题目传送门https://www.luogu.com.cn/problem/P14076前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道经典的树上路径贪心问题。我们需要从首都出发遍历所有节点并且要求总路径最短。模型转化题目中的 n 座城市和 n-1 条双向道路且任意两座城市均可到达这在图论中被称为树Tree。首都 1 号节点就是这棵树的根节点。核心贪心策略在树上遍历所有节点最朴素的做法是“深度优先搜索DFS”从根节点出发走到每一个叶子节点然后原路返回。在这个过程中每一条边都会被经过两次去一次回一次。因此所有边的长度总和乘以 2就是遍历所有节点并回到起点的总代价。但是题目有一个关键条件“车队最后可以不返回首都”。这意味着我们可以省去从“最远的那个城市”返回首都的那段路程。为了让总路程最小我们省去的这段路程必须尽可能长。数学公式最终的答案 所有边的长度总和 × 2 - 从首都出发能到达的最远距离。代码分块详细解释1. 头文件、常量与全局变量定义#includebits/stdc.h using namespace std; #define ll long long // 定义长整型别名 ll因为边权和最大可达 1e14必须用 long long const int N1e510; // 定义常量 N表示城市数量的最大范围 vectorpairint,ll g[N]; // 定义邻接表 gg[u] 存储与城市 u 相连的 {相邻城市, 道路长度} ll max_dist0; // 定义变量 max_dist用来记录首都到最远城市的距离详细分析这部分搭建了图论问题的基础数据结构。由于题目中边的长度l_i最大可达 109且最多有 10^5 条边总路程可能达到 10^14 级别远远超出int的范围因此必须使用long long。vectorpairint,ll g[N]是存储无向图树的标准邻接表写法pair的第一个元素存相邻节点第二个元素存边权。2. 深度优先搜索DFS求最远距离// 定义深度优先搜索函数u 是当前城市fa 是父节点防止走回头路d 是当前走过的距离 void dfs(int u, int fa, ll d){ max_dist max(max_dist, d); // 每次到达一个节点都尝试更新最远距离 for(auto edge : g[u]){ // 遍历当前城市 u 的所有相邻道路 int v edge.first; // 相邻的城市编号 ll w edge.second; // 这条道路的长度 if(v ! fa){ // 如果相邻城市不是父节点即不是回头路 dfs(v, u, d w); // 继续向下深搜距离累加当前道路长度 } } }详细分析这个 DFS 函数的作用是求树的“加权直径”从根节点出发的最长路径。防止死循环在树中遍历必须传递父节点fa通过if(v ! fa)确保搜索只向子节点延伸不会在两个节点之间来回横跳。距离累加d w实时维护从首都根节点到当前节点v的总路径长度。全局更新每当 DFS 走到一个节点就将其距离与全局变量max_dist进行比较最终max_dist就会保存从首都出发能到达的最远城市的距离。3. 主函数建图与边权累加int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭标准流同步提升输入输出效率 cin.tie(0); // 解除 cin 与 cout 的绑定进一步加快读取速度 int n; // 变量 n表示城市的总数 ll sum 0; // 定义变量 sum用来累加所有道路的长度总和 cin n; // 读入城市的数量 n for(int i 1; i n; i){ // 循环读入 n-1 条道路的信息 int u, v; // 定义临时变量 u 和 v代表一条道路连接的两个城市 ll len; // 定义临时变量 len代表这条道路的长度 cin u v len; // 读入这条道路连接的两个城市编号以及长度 g[u].push_back({v, len}); // 在邻接表中添加 u 到 v 的连接 g[v].push_back({u, len}); // 在邻接表中添加 v 到 u 的连接因为是无向图 sum len; // 累加所有道路的长度 }详细分析主函数的前半部分负责数据的读取和图的构建。sum len这一步非常关键它直接计算出了整棵树所有边的权值之和。由于是无向图添加边时需要双向添加u-v和v-u都要加保证 DFS 时能正确遍历到所有相邻节点。4. 核心计算与输出dfs(1, 0, 0); // 从首都1号城市开始进行 DFS父节点设为 0初始距离为 0 cout 2 * sum - max_dist; // 输出最短总路程所有边走两倍的代价减去最远的一条回程 return 0; // 程序结束 }详细分析这是整个算法的收尾。调用dfs(1, 0, 0)从根节点开始遍历求出最远回程距离max_dist。最后利用贪心公式2 * sum - max_dist直接得出答案。例如在样例 1 中总边权和为 61512两倍是 24从首都 1 出发最远能走到 4 号城市距离为 156所以最终答案是 24 - 6 18。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点数据类型#define ll long long使用 64 位长整型防止 105 条边、每条边 109 权值累加时发生数据溢出图存储vectorpairint,ll g[N]邻接表存无向图完美适配 n ≤ 105 的稀疏图比邻接矩阵更节省空间DFS 防回头if(v ! fa)记录父节点并剪枝避免在树的双向边中陷入无限递归死循环贪心公式2 * sum - max_dist核心数学推导将复杂的“遍历所有节点的最短路径”问题转化为简单的“总边权*2 - 最长单程”IO 优化ios::sync_with_stdio(false)提升输入输出效率解决 105 级别数据量下cin/cout可能导致的超时问题