要用最少费用建设一条公路网,将五个城市连接起来,使它们可以相互到达,已知建设用与公路长度成正比,那么该问题可以看成是()。A. 最大流量问题B. 最短路问题C. 最小树问题D. 最小费用最大流问题

本题考察图论中不同网络优化问题的实际应用场景，核心是区分最小树、最短路、最大流量、最小费用最大流等问题的定义与目标。

关键分析

题目要求“用最少费用建设一条公路网，将五个城市连接起来，使它们可以相互到达”，且“建设费用与公路长度成正比”。这意味着：

1. 连接所有城市且相互到达：等价于图论中“连通所有顶点”的要求；
2. 费用最少：因费用与长度成正比，故需总长度最短，进而总费用最少；
3. 最少的公路网：为避免冗余（如环），需选择“边数最少的连通图”——树结构（$n$个顶点的树有$n-1$条边，是连通图中边数最少的）。

选项排除

• A. 最大流量问题：关注网络中从源点到汇点的最大运输能力，与“连接所有城市”无关，排除；
• B. 最短路问题：仅求两点间最短路径，不涉及“连接所有城市”，排除；
• C. 最小树问题：目标是找到连通所有顶点的最小总权树（此处权为长度，对应费用），完全匹配题目要求；
• D. 最小费用最大流在最大流前提下的最小费用，与“连接所有城市”无关，排除。