查看“︁1994年美赛A题：通信网络的文件传输调度”︁的源代码

'''1994年美赛A题：通信网络的文件传输调度'''是1994年MCM的A题，英文原题名为''The Communications Network Problem''。

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

== 网络与并发占用 ==

公司每天需要在各部门间交换前一日销售统计、当前生产指导等文件，希望尽快完成全部传输。用顶点<math>V_y</math>代表计算机，用边<math>e_x</math>代表要在两个端点计算机之间传输的一个文件。

<math>T(e_x)</math>为文件传输耗时，<math>C(V_y)</math>为一台计算机同时参与传输的容量。例如容量为1表示该机在任何时刻只能参与一次传输。'''每次传输在整个持续时间内都占用两个端点计算机'''。

目标是安排各文件的传输时间，使全部传输完成的最晚时刻最小；这一总工期称为'''makespan'''。

[[File:Gezhi-contest-figures-1994-comap-A-network-example.png|frame|center|alt=原始文件传输网络示例，有五个顶点及各边耗时与顶点容量|原题图1：文件传输网络示例，顶点容量和边耗时均保留。]]

== 完整网络与文件时间 ==

[[File:Gezhi-contest-figures-1994-comap-A-network-ab.png|frame|center|alt=情形A B的原始树状网络，保留28个顶点与27条边的编号|原题图2：情形A、B共用的28顶点网络。]]

共有28台计算机。原图中的连接关系改列如下：边1—27构成情形A、B的网络；情形C保留这些边并增加28—42。下面的耗时适用于情形B、C；情形A将前27条边的耗时全部改为1。

<div class="math-table-scroll" role="region" aria-label="全部42项文件传输及其端点" tabindex="0">
{| class="wikitable"
! 文件边号 !! 端点计算机 !! 另一个端点 !! B/C传输耗时
|-
| 1 || V3 || V1 || 3
|-
| 2 || V3 || V2 || 4.1
|-
| 3 || V5 || V7 || 4
|-
| 4 || V5 || V4 || 7
|-
| 5 || V6 || V5 || 1
|-
| 6 || V6 || V3 || 8
|-
| 7 || V8 || V6 || 3.2
|-
| 8 || V8 || V9 || 2.4
|-
| 9 || V9 || V13 || 5
|-
| 10 || V9 || V10 || 8
|-
| 11 || V10 || V12 || 1
|-
| 12 || V10 || V11 || 4.4
|-
| 13 || V14 || V8 || 9
|-
| 14 || V14 || V15 || 3.2
|-
| 15 || V15 || V19 || 2.1
|-
| 16 || V15 || V16 || 8
|-
| 17 || V16 || V18 || 3.6
|-
| 18 || V16 || V17 || 4.5
|-
| 19 || V14 || V20 || 7
|-
| 20 || V20 || V24 || 7
|-
| 21 || V24 || V26 || 9
|-
| 22 || V24 || V25 || 4.2
|-
| 23 || V26 || V27 || 4.4
|-
| 24 || V26 || V28 || 5
|-
| 25 || V20 || V21 || 7
|-
| 26 || V21 || V22 || 9
|-
| 27 || V21 || V23 || 1.2
|-
| 28 || V18 || V11 || 6
|-
| 29 || V15 || V13 || 1.1
|-
| 30 || V17 || V19 || 5.2
|-
| 31 || V16 || V19 || 4.1
|-
| 32 || V19 || V22 || 4
|-
| 33 || V23 || V24 || 7
|-
| 34 || V24 || V3 || 2.4
|-
| 35 || V26 || V1 || 9
|-
| 36 || V25 || V28 || 3.7
|-
| 37 || V3 || V7 || 6.3
|-
| 38 || V12 || V4 || 6.6
|-
| 39 || V10 || V5 || 5.1
|-
| 40 || V10 || V6 || 7.1
|-
| 41 || V13 || V14 || 3
|-
| 42 || V8 || V20 || 6.1
|}
</div>

原图的某些末端顶点标签在扫描件中不清，以上编号以完整28点编号和情形C清晰图对应：边23连接<math>V_{26},V_{27}</math>，边24连接<math>V_{26},V_{28}</math>。

== 情形A：相同文件耗时 ==

28个部门每天传输27个文件，即边1—27。所有文件耗时为1，所有计算机容量为1。

给出最优调度和最小工期，论证该工期确实不可能进一步减少，说明求解方法，并讨论方法是否适用于文件耗时、计算机容量和图结构均任意的一般情形。

== 情形B：文件大小不同 ==

仍使用边1—27和容量1，但耗时取上表给出的数值。

求最优调度和最小工期，说明最优性的依据与求解方法，讨论对一般情形的适用性，并评论特别或出乎预料的结果。

[[File:Gezhi-contest-figures-1994-comap-A-network-c.png|frame|center|alt=情形C原始网络图，保留原有连接及新增的28至42号边|原题图3：情形C扩容后的网络，含新增连接。]]

== 情形C：扩容并增加传输 ==

使用全部42条边及其给定时间。部分计算机升级，并发容量如下；未升级者仍为1。

<div class="math-table-scroll" role="region" aria-label="情形C的28台计算机容量" tabindex="0">
{| class="wikitable"
! 计算机 !! 并发容量
|-
| V1 || 2
|-
| V2 || 2
|-
| V3 || 1
|-
| V4 || 1
|-
| V5 || 1
|-
| V6 || 1
|-
| V7 || 1
|-
| V8 || 1
|-
| V9 || 2
|-
| V10 || 3
|-
| V11 || 1
|-
| V12 || 1
|-
| V13 || 1
|-
| V14 || 2
|-
| V15 || 1
|-
| V16 || 2
|-
| V17 || 1
|-
| V18 || 1
|-
| V19 || 1
|-
| V20 || 1
|-
| V21 || 1
|-
| V22 || 2
|-
| V23 || 1
|-
| V24 || 1
|-
| V25 || 1
|-
| V26 || 2
|-
| V27 || 1
|-
| V28 || 1
|}
</div>

给出能够找到的最好调度及工期，讨论能否证明它是这个网络的最小工期，说明方法，并解释特别或出乎预料的结果。

== 原题与来源 ==

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

[[分类:美赛赛题]]