查看“︁1991年美赛A题：直角通信网络的斯坦纳树”︁的源代码

'''1991年美赛A题：直角通信网络的斯坦纳树'''是1991年MCM的A题，英文原题名为''The Steiner Tree Problem''。

返回[[1991年美赛赛题]]。

== 线路与辅助站点 ==

连接通信站的线路成本与长度成正比。在原有站点之外增加辅助站点，可以让若干线路共用部分路径，从而降低总成本。这类允许增加辅助连接点的树形网络称为斯坦纳树。

题目先用平面直线网络作背景说明：增加辅助点可相对于通常的最小生成树节省最多约13.4%，即<math>1-sqrt{3}/2</math>；有<math>n</math>个既定站点时，构成最便宜斯坦纳树不需多于<math>n-2</math>个辅助点。原图的三点示例中，两条长为<math>sqrt3</math>的边可换为三条长度为1的边。

实际要研究的本地网络则'''只允许水平和竖直线路'''，以棋盘式的直角路径计算长度。各段线路成本直接等于其长度，所有新增辅助站点都必须位于'''整数格点'''。

== 九个既定站点 ==

<div class="math-table-scroll" role="region" aria-label="九个通信站坐标" tabindex="0">
{| class="wikitable"
! 站点 !! 横坐标 !! 纵坐标
|-
| a || 0 || 15
|-
| b || 5 || 20
|-
| c || 16 || 24
|-
| d || 20 || 20
|-
| e || 33 || 25
|-
| f || 23 || 11
|-
| g || 35 || 7
|-
| h || 25 || 0
|-
| i || 10 || 3
|}
</div>

== 任务 ==

# 为上述九个站点建立连接全部站点、总线路成本最小的树形网络，允许按题设增加整数格点辅助站。
# 再计入站点成本：一个站点若连接了<math>d</math>条边，即度数为<math>d</math>，其成本为<math>w,d^{3/2}</math>。取'''<math>w=1.2</math>'''，重新寻找总成本最小的树。
# 尝试推广这一问题，说明方法或结论能够如何扩展。

新增辅助站同样属于第二问计费的站点，需把站点成本和线路成本一起考虑。

== 原题与来源 ==

[https://www.contest.comap.com/undergraduate/contests/matrix/PDF/1991/1991A.pdf COMAP官方题面（PDF）]；题号和年份按[https://www.contest.comap.com/undergraduate/contests/matrix/index.html COMAP历年赛题矩阵]。核对日期：2026年9月22日。

[[分类:美赛赛题]]