Optprob/Прокладка водопровода в селе

Муниципалитет хочет разработать способ доставки воды из муниципального водохранилища «D» в 7 сельских домов, не обязательно напрямую, с наименьшими возможными затратами.

Возможные варианты трубопроводов между водохранилищем и домами с соответствующими затратами в денежных единицах приведены в следующей таблице (приведен только верхний треугольник симметричной матрицы):

.	D	C1	C2	C3	C4	C5	C6	C7
D	x	10	12	14	x	x	x	x
C1	x	x	x	x	3	x	x	x
C2	x	x	x	x	2	4	x	x
C3	x	x	x	x	x	3	x	x
C4	x	x	x	x	x	3	5	6
C5	x	x	x	x	x	x	7	5
C6	x	x	x	x	x	x	x	4
C7	x	x	x	x	x	x	x	x

Например, проезд между 2-м и 5-м домами стоит 4 денежные единицы.

Рассчитайте все возможные способы соединения так, чтобы общая стоимость была минимальной. (визуализируйте графы).

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.