Теоретический материал
Решение задачи о назначениях (Венгерский алгоритм)
В данной задаче требуется найти в двудольном графе полное паросочетание минимального веса. Не снижая общности мы можем считать, что такое паросочетание всегда существует (двудольный граф можно дополнить до полного ребрами с весом, превышающим сумму остальных весов ребер данного графа и при необходимости удалить подобные ребра из ответа).
Лемма 1. Если веса всех ребер графа, инцидентных какой-либо вершине, увеличить (уменьшить) на одно и то же число, то искомое паросочетание является искомым и в новом графе.
Одно из следствий – мы можем считать, что веса всех ребер у нас неотрицательные.
Лемма 2. Если веса всех ребер неотрицательные, и некоторое паросочетание состоит из ребер нулевого веса, то оно искомое.
Схема решения
for i:= 1 to n do begin
{каждой вершине одного из множеств находим назначение}
for j:=1 to n do min[j]:=maxint;
repeat
fillchar(new,sizeof(new),false);
f := dfs(i);{пару ищем только по ребрам нулевого веса}
if not f then begin
1) {ищем минимальный элемент в помеченных dfs строках new[i]=true
среди элементов столбцов не вошедших в текущую цепочку
(res[j] = 0) or (not new[res[j]])
обозначим найденный элемент del}
2) {перестраиваем матрицу так:
из всех помеченных dfs строк вычитаем del
ко всем вошедшим в текущую цепочку столбцам прибавляем del
end;
until f;
end;
for j:= 1 to n do
writeln(j,' ',res[j])
|
1 |
3 |
2 |
3 |
|
2 |
1 |
3 |
6 |
|
4 |
2 |
6 |
8 |
|
4 |
5 |
2 |
7 |
|
0 |
2 |
1 |
2 |
|
2 |
1 |
3 |
6 |
|
4 |
2 |
6 |
8 |
|
4 |
5 |
2 |
7 |
|
0 |
2 |
1 |
2 |
|
1 |
0 |
2 |
5 |
|
4 |
2 |
6 |
8 |
|
4 |
5 |
2 |
7 |
|
0 |
2 |
1 |
2 |
|
1 |
0 |
2 |
5 |
|
2 |
0 |
4 |
6 |
|
4 |
5 |
2 |
7 |
|
0 |
3 |
1 |
2 |
|
0 |
0 |
1 |
4 |
|
1 |
0 |
3 |
5 |
|
4 |
6 |
2 |
7 |
|
0 |
3 |
0 |
1 |
|
0 |
0 |
0 |
3 |
|
1 |
0 |
2 |
4 |
|
4 |
7 |
2 |
7 |
и т.д.