Кабельное подключение (ОКД НТИ 20/21 :: ТБС)
Легенда
Прогресс не стоит на месте, в одном городе потребовалось заменить устаревшую систему телевещания на цифровую. Для обеспечения наилучшего качества телевещания, было решено установить комплекс передающих антенн для полного обхвата территории города. Ретранслировать информацию по воздуху не очень рационально, поэтому антенны соединяются между собой кабелями. Но любое обеспечение связи в таких масштабах связано с ресурсами, а ресурсы нужно расходовать бережно.
Вам известны координаты точек расположения передающих антенн на условной декартовой плоскости (условимся, что первая точка соответствует главной передающей антенне). Необходимо соединить все точки в единую систему так, чтобы минимизировать суммарную длину проброшенных кабелей между антеннами и только её. Линии протягиваются между парами точек, к одной точке может быть подключено несколько линий. В этой задаче мы не учитываем потери и прочие параметры.
Принцип решения
- Минимальное дерево (реализация)