Венгерский алгоритм решения задачи о назначениях

                way[i] = 0;

            }

            const int INF = 2147483647;

 

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

Итак, создаем внешний  цикл for, который будет добавлять нам строки из матрицы одну за одной. Заносим в нулевой элемент массива паросочетаний текущую строку, создаем массив минимумов по столбцам (заполняя его максимальным числом) и массив столбцов, которые мы уже посетили (изначально все его элементы заполняем как false):

 

            for (int i = 1; i <= n; i++)

            {

                p[0] = i;

                int j0 = 0;

                int[] minv = new int[m + 1];

                bool[] used = new bool[m + 1];

                for (int h = 0; h <= m; h++)

                {

                    minv[h] = INF;

                    used[h] = false;

                }

 

Далее следует цикл do-while, который работает, пока не будет найден свободный столбец j0. На каждой итерации этого цикла мы отмечаем посещенным столбец j0, полученный на прошлой итерации (изначально он нулевой), а также новую строку i0 – смежную в паросочетании столбцу j0 (изначально берется новая добавленная строка i). Кроме того, в обязательном порядке пересчитываем минимумы по столбцам (они изменились в следсвие добавления новой строки) и заодно пересчитываем глобальный минимум delta.

 

                do

                {

                    used[j0] = true;

                    int i0 = p[j0], delta = INF, j1 = 0;

                    for (int j = 1; j <= m; j++)

                    {

                        if (!used[j])

                        {

                            int cur = a[i0, j] - u[i0] - v[j];

                            if (cur < minv[j])

                            {

                                minv[j] = cur;

                                way[j] = j0;

                            }

                            if (minv[j] < delta)

                            {

                                delta = minv[j];

                                j1 = j;

                            }

                        }

                    }

 

После этого пересчитываем  потенциал u[] и v[] в соответствии с алгоритмом, изменяем минимумы по столбцам и в качестве нового столбца j0 берем столбец j1, на котором был найден минимум.

 

                    for (int j = 0; j <= m; j++)

                    {

                        if (used[j])

                        {

                            u[p[j]] += delta;

                            v[j] -= delta;

                        }

                        else

                        {

                            minv[j] -= delta;

                        }

                    }

                    j0 = j1;

                } while (p[j0] != 0);

 

По окончании цикла  мы найдем увеличивающую цепочку, развернуть которую нам поможет массив way[] и, собственно, сами паросочетания p[]:

 

                do

                {

                    int j1 = way[j0];

                    p[j0] = p[j1];

                    j0 = j1;

                } while (j0 != 0);

 

            }

 

Алгоритмы завершает работу когда будут добавлены все  строки матрицы, а ответ будет  храниться в наших паросочетания  p[]. Чтобы сделать ответ более привычным: каждой строке j сопоставить найденный столбец ans[j] необходимо дополнительно пройтись по паросочетаниям:

 

 

            int[] ans = new int[n + 1];

            ans[0] = 0;

            for (int j = 1; j <= m; j++)

                ans[p[j]] = j;

            Console.WriteLine("Распределение работников:");

            for (int j = 1; j <= n; j++)

                Console.WriteLine(j + "->" + ans[j]);

            Console.WriteLine("Суммарные затраты: {0}", -v[0]);

        }

    }

}

 

Получив массив ответов ans[] выводим его на экран. Удивительно, но нам даже не потребуется делать каких-либо дополнительных вычислений для определения суммарных минимальных затрат: они уже были посчитаны в ходе алгоритма и сохранены в нулевом элементе массива v[], с тем лишь отличием, что там затраты хранятся с противоположным знаком. Остается только умножить v[0] на минус единицу и вывести на экран суммарные затраты.