Задача 22.
Имеется N точек и M проводков. Проводком можно соединить некоторую пару различных точек, причем пара может быть соединена не более чем одним проводком. Все проводки должны быть использованы.
Пусть Di - количество проводков, которые будут соединены с точкой с номером i, i=1, ..., N.
Необходимо соединить N точек с помощью M проводков таким образом, чтобы сумма S=D1*D1 + D2*D2 + ... + Dn*Dn была максимальной.
Вывести величины Di в неубывающем порядке и. по требованию
(priznak=1), список соединений.
ВВОД:
<Введите N:> N (N<=100)
<Введите M:> M (M<=1000)
<PRIZNAK=> PRIZNAK
ВЫВОД:
<Результирующая конфигурация:> Di в неубывающем порядке.
<Сумма S> S
<Список соединений>
<Точку 1 соединить с> список точек
.....
<Точку N соединить с> список точек
|
Решение задачи 22.
Показывается, что точное решение есть максимум из двух
решений, полученных при помощи следующих эвристик:
1) Вершину 1 соединяем последовательно с вершинами 2, 3, ...,N.
Вершину 2 соединяем последовательно с вершинами 3,4,...,N.
......
Вершину i соединяем последовательно с вершинами i+1, i+2, ...,N.
......
и так до тех пор, пока хватит проводков.
2) Вершину 2 соединяем с вершиной 1.
Вершину 3 соединяем последовательно с вершинами 1,2.
......
Вершину i соединяем последовательно с вершинами i-1, i-2,...,1.
......
и так до тех пор, пока хватит проводков.
|
