Задача о назначении. Не уверен в правильности решения.

[Nogin Anton]

Здравствуйте! Стоит следующая задача.

В сельской местности работает N передвижных магазинов. По завершении
работы все они должны переехать из тех населенных пунктов, где они находятся в другие.
Обозначим за $A_{ij}$ расстояние от i-того исходного населенного пункта к j-тому населенному
пункту назначения. Составить план перемещения передвижных магазинов так, чтобы сум-
марное пройденное расстояние оказалось минимальным. В качестве демонстрационного
примера взять следующую матрицу A:

$\begin{array}{|l|c|r|l|} \hline - & 1 & 2 & 3 \\ \hline A & 32 & 11 & 19 \\ \hline B & 41 & 54 & 23 \\ \hline C & 47 & 34 & 41 \\ \hline \end{array}$

В матрице исходные населенные пункты обозначены буквами, пункты назна-
чения - цифрами.

Для решения поставленной задачи использовал Венгерский Алгоритм. Для начала нужно сделать так, чтобы в каждом столбце и в каждой строке был хотя бы один нулевой элемент.

Методом "вычитания" минимальных элементов получил следующую матрицу:

$\begin{array}{|l|c|r|l|} \hline - & 1 & 2 & 3 \\ \hline A & 8 & 0 & 8 \\ \hline B & 5 & 31 & 0 \\ \hline C & 0 & 0 & 7 \\ \hline \end{array}$

Венгерский алгоритм.

(Оффтоп)

1. Найти строку с наименьшим количеством нулей.
2. Знаком "+" отметить один из нулей этой строки. А знаком "-" все остальные нули этой строки и того столбца, в котором находится этот ноль.
3. Повторяем эту процедуру для остальных строк, пока есть неотмеченные нули.
4. Если число нулей со знаком "+" равно n, то получено оптимальное решение.

$\begin{array}{|l|c|r|l|} \hline - & 1 & 2 & 3 \\ \hline A & 8 & 0^+ & 8 \\ \hline B & 5 & 31 & 0^+ \\ \hline C & 0^+ & 0^- & 7 \\ \hline \end{array}$

Число нулей со знаком "+" равно n. Скажите, всё ли верно я сделал?
Заранее спасибо!

[Yu_K]

A B C
1 2 3 (длина пути 127)
1 3 2 (89)
2 1 3 (93)
2 3 1 (81)
3 1 2 (94)
3 2 1 (120)


Можно же все простым перебором проверить - всего 6 вариантов выбора путей - минимальная длина 81.

[Cash]

Да, все правильно вы сделали.

[Nogin Anton]

Большое спасибо.

P.S. по заданию нужно было именно венгерским методом.