[GESP202509 六级] 货物运输

凤凰_天之神_z_io

2026-09-27 11:09:40

发布于：广东

10阅读

0回复

0点赞

ACGO_gif_加油喝彩

题意解析

题目告诉我们，A国有 $n$ 座城市和 $n-1$ 条道路，所有城市都能互相到达，这种没有环的结构在计算机里叫作"树"。现在你要开一辆货车从一号城市（首都）出发，把所有城市都走遍，最后不需要回到首都。我们的目标是让货车开过的总路程最短。
数据范围：城市数量 $n≤10^5$ ,单条道路长度可达 $10^9$ .这暗示总距离极大，必须用long long储存；同时算法必须在 $O(n)$ 左右的线性时间内完成，否则一定会超时。

抽丝剥茧：如何思考

1.朴素想法：全排列暴力搜索路线
面对"走遍所有点求最短路"的问题，最容易想到的是把所有可能的路线都试一遍:

第一步：列举所有访问顺序。假设我们要给出一个一次拜访城市的清单，比如先去2再去3，我们尝试把所有城市的排列组合全部列举出来。

第二步：模拟行走并计算距离。根据写好的清单，模拟货车在城市间移动。因为城市道路没有坏，任意两座城市之间只有唯一的最短路径。把清单上一路上经过的道路长度全部累加起来。

第三步：比较并选出最小距离。记录每一种路线清单算出的总距离，最后挑出那个最小的结果作为答案。

2.遇到瓶颈

我们来算算时间帐。对于 $n$ 座城市，全排列的路线数量是 $n!$ ( $n$ 的阶乘）。当 $n=12$ ,
$12!≈4.7 * 10^8$ ,对于每一条路线，我们需要写一个循环去模拟走过这12个城市，累加距离。这大约需要执行12次加法运算，所以运算量超过 $5*10^9$ ，彻底超时。本题 $n = 10^5$ ,远大于12，更加会超时！这说明"纠结访问顺序"这条路走不通。

寻找规律与优化策略

假设A过只有4座城市，道路连接和长度如下：

        (首都）
          1
         / \
  100km /   \  10km
       /     \
      2       3
               \
                \ 20km
                 \
                  4

上图可见

1号是首都
道路共有3条：1_{2（长100）、1}3（长10）、3~4（长20）
所有道路长度之和 $= 100 + 10 + 20 = 130km$ 。

假设：要求"必须回到首都"

想想你是一个快递员，从 $1$ 出发，要把包裹送到 $2,3,4,$ 最后必须回 $1$ 下班。
因为这地图没有环路（像树杈一样），走进死胡同就只能原路折返。

你的路线只能是这样(比如先去左边,再去右边):
出发 $1→2→1→3→4→3→1$ 下班回家

我们来看看每条路你走了几次:

1到2的路: 去一次, 回一次 (走了2次)
1到3的路: 去一次, 回一次 (走了2次)
3到4的路: 去一次, 回一次 (走了2次)

发现规律了吗?

只要你最后回到起点,所有的路你都必定、且只能走恰好两次(一趟去, 一趟回)。
此时的总路程 $=$ 所有道路之和的 $2$ 倍$ = 130 * 2 = 260 km。$
这个 $260 km$ ,是我们接下来计算的“基准线”。

题目真实情况“不用回首都”

现在老板说:“送到最后一个城市你就可以直接在那儿下班,不用回首都了!”
既然不用回首都,这意味着你最后停在哪个城市,从首都到那个城市的“回程路”就省下来了!

我们来看看停在不同城市的区别:

方案 A:最后停在4号城市(把4当最后一站)

路线:先去左边送2,折返回来,再去右边送3,4并在4下班。
实际走法: $1 → 2 → 1 → 3 4 $(停!)
算算每条路走了几次:
- 1-2 道路:走了 $2$ 次(去,回)
- 1-3 道路:走了 $1$ 次(去了就没回来)
- 3-4 道路:走了 $1$ 次(去了就没回来)
实际总路程: $100 × 2 + 10 × 1 + 20 x 1 = 230 km$ 。
$230 = 260-30$ 。(即:总路程的 $2$ 倍- 首都到 $4$ 号城市的距离)

方案 B:最后停在2号城市(把2当最后一站)

路线:先去右边送3,4,折返回来,再去左边送2并在2下班。
实际走法: $1 → 3 → 4 → 3 → 1 → 2$ (停!)
算算每条路走了几次:
- 1-3 道路:走了 $2$ 次(去,回)
- 3-4 道路:走了 $2$ 次(去,回)
- 1-2 道路:走了 $1$ 次(去了就没回来)
实际总路程: $10 × 2 + 20 × 2 + 100 x 1 = 160 km$ 。
$160 = 260 - 100$ 。(即:总路程的2倍- 首都到2号城市的距离)

总结:

通过对比方案 $A(230 km)$ 和方案 $B (160 km)$ ,方案 B 明显更短,也就是题目要求的“最小化路程”。

为什么方案更短?
因为方案 $B$ 最后一站选了 $2$ 号城市,而1到2的距离是 $100 km$ 。

你把哪座城市作为最后一站,你就能省下首都到那座城市的折返距离。

我们要想让货车开的总路程最短,当然是希望省下来的回程路越长越好!

这就好比你有两张抵扣券,一张抵扣 $30$ 元,一张抵扣 $100$ 元,为了花钱最少,你肯定用那张 $100$ 元的对不对?

所以:

想让总路程最小要减去的回程路必须最大必须把离首都最远的城市作为最后一站。
最终顺理成章得出公式:最短总路程 $=$ 所有道路总长 x $2 - $首都到最远城市的距离。

优化后的解题过程:

第一步:搭建地图并累加路程(准备基准线)

在读取数据的同时做两件事:一是把城市间的双向连接关系存进数组(代码里的 $e$ );二是顺手把所有道路的长度累加到变量中,为后面计算 $s$ × $2$ 做准备。

第二步:寻找最远城市(找出能“省下”的最长路)

写一个DFS(深度优先搜索) 函数,从首都( $1$ 号)开始顺着路一直往下探。

每走到一个城市,就看看当前距离是不是打破了最远纪录,如果是,就更新给变量 $mx$ 。
为了防止“原地打转”,每次往下走时,都避开刚才过来的那个城市(不走回头路)。

第三步:套用公式,一秒出结果

探路结束后,地图的总路长 $s$ 和最远距离 $mx$ 都拿到了。直接让计算机输出 $s$ x $2$ - $mx$ ,不需要任何复杂的路径模拟,直接得出最短总路程!

复杂度分析

通过上述推导,我们只需要把所有路权加起来,再顺着道路找一遍离首都最远的城市即可。时间复杂度为 $O(N)$ ,空间复杂度为 $O(N)$ ,这个复杂度能在规定时间内轻松通过全部测试点!

#include<bits/stdc++.h>
using namespace std;
const int man = 1e5 + 10;
int n;
// e用于存放城市间的道路连接关系。pair的第一项是到达的城市,第二项是道路长度
___________________________________;
long long s, mx; //s 存放所有道路长度之和,mx 存放首都到最远城市的距离

// dfs函数:深度优先搜索(一种顺着路走到底再回头的探路方法)
void dfs(_________________________){
	// 每走到一个城市,都尝试更新一下“最远距离 mx"
	_________________;
	
	// 遍历当前城市连接的所有道路
	_______________________
		// 只要这条路不是通向刚才过来的城市(不走回头路)
		_________________
			// 继续顺着路往下走,把当前道路长度加到总距离 d 里面
			________________________________
		}
	}
}
int main(){
	cin >> n;
	e.resize(n + 1);
	for (int i = 1; i < n; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		// 建立双向道路
		______________________;
		______________________;
		// 边读入,边把所有道路的长度累加到中
		_______;
	}
	
	// 从 1号城市(首都)开始探路,初始来源设为0,初始距离设为 0
	____________;
	// 输出最终结论公式:所有道路长度之和 * 2 - 首都到最远城市的距离
	_________________________;
	return 0;
}