Question

一个组织有 $30$ 名员工，其中 $20$ 人使用 A 品牌电脑，另外 $10$ 人使用 B 品牌电脑。出于安全原因，电脑只能彼此相连，且只能用电缆连接。电缆只能把一台 A 品牌电脑和一台 B 品牌电脑相连。如果两名员工的电脑直接由电缆相连，或可以通过一系列相连的电脑转发消息，则他们可以相互通信。最初没有任何电脑与其他电脑相连。一名技术员任意选择一台每种品牌的电脑，并在它们之间安装电缆，前提是这对电脑之间还没有电缆。技术员在每名员工都能相互通信时停止。最多可能使用多少根电缆？

An organization has $30$ employees, $20$ of whom have a brand A computer while the other $10$ have a brand B computer. For security, the computers can only be connected to each other and only by cables. The cables can only connect a brand A computer to a brand B computer. Employees can communicate with each other if their computers are directly connected by a cable or by relaying messages through a series of connected computers. Initially, no computer is connected to any other. A technician arbitrarily selects one computer of each brand and installs a cable between them, provided there is not already a cable between that pair. The technician stops once every employee can communicate with each other. What is the maximum possible number of cables used?

$190$

$191$

$192$

$195$

$196$

答案：B

知识点：图论极端原理

难度评级：1840

解答：

技术员不断加电缆，直到图变为连通。为了最大化电缆数，要让网络尽可能久地保持不连通：留下一台 A 品牌电脑孤立，并把其余 $19$ 台 A 品牌电脑与全部 $10$ 台 B 品牌电脑完全相连。

这样在仍不连通时使用了 $19 \cdot 10 = 190$ 根电缆。下一根电缆连接最后一台 A 品牌电脑，使所有人连通，总数为 $190 + 1 = 191$ 。

所以正确答案是 B。

The technician keeps adding cables until the graph becomes connected. To maximize the count, keep the network disconnected for as long as possible: leave a single brand A computer isolated and fully connect the remaining $19$ brand A computers to all $10$ brand B computers.

That uses $19 \cdot 10 = 190$ cables while still disconnected. The next cable connects the last brand A computer, joining everyone, for a total of $190 + 1 = 191.$

Thus, the correct answer is B.

2021 AMC 12A Fall 第 16 题

答案：B

难度评级：1840

解答：

其他年份的第 16 题