1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| /* Венгерский алгоритм.
* Даниил Швед, 2008. danshved [no-spam] gmail.com
* Реализация навеяна псевдокодом А.С.Лопатина из книги
* "Оптимизация на графах (алгоритмы и реализация)".
*/
#include <vector>
#include <limits>
using namespace std;
typedef pair<int, int> PInt;
typedef vector<int> VInt;
typedef vector<VInt> VVInt;
typedef vector<PInt> VPInt;
const int inf = numeric_limits<int>::max();
/*
* Решает задачу о назначениях Венгерским методом.
* matrix: прямоугольная матрица из целых чисел (не обязательно положительных).
* Высота матрицы должна быть не больше ширины.
* Возвращает: Список выбранных элементов, по одному из каждой строки матрицы.
*/
VPInt hungarian(const VVInt &matrix) {
// Размеры матрицы
int height = matrix.size(), width = matrix[0].size();
// Значения, вычитаемые из строк (u) и столбцов (v)
VInt u(height, 0), v(width, 0);
// Индекс помеченной клетки в каждом столбце
VInt markIndices(width, -1);
// Будем добавлять строки матрицы одну за другой
for(int i = 0; i < height; i++) {
VInt links(width, -1);
VInt mins(width, inf);
VInt visited(width, 0);
// Разрешение коллизий (создание "чередующейся цепочки" из нулевых элементов)
int markedI = i, markedJ = -1, j;
while(markedI != -1) {
// Обновим информацию о минимумах в посещенных строках непосещенных столбцов
// Заодно поместим в j индекс непосещенного столбца с самым маленьким из них
j = -1;
for(int j1 = 0; j1 < width; j1++)
if(!visited[j1]) {
if(matrix[markedI][j1] - u[markedI] - v[j1] < mins[j1]) {
mins[j1] = matrix[markedI][j1] - u[markedI] - v[j1];
links[j1] = markedJ;
}
if(j==-1 || mins[j1] < mins[j])
j = j1;
}
// Теперь нас интересует элемент с индексами (markIndices[links[j]], j)
// Произведем манипуляции со строками и столбцами так, чтобы он обнулился
int delta = mins[j];
for(int j1 = 0; j1 < width; j1++)
if(visited[j1]) {
u[markIndices[j1]] += delta;
v[j1] -= delta;
} else {
mins[j1] -= delta;
}
u[i] += delta;
// Если коллизия не разрешена - перейдем к следующей итерации
visited[j] = 1;
markedJ = j;
markedI = markIndices[j];
}
// Пройдем по найденной чередующейся цепочке клеток, снимем отметки с
// отмеченных клеток и поставим отметки на неотмеченные
for(; links[j] != -1; j = links[j])
markIndices[j] = markIndices[links[j]];
markIndices[j] = i;
}
// Вернем результат в естественной форме
VPInt result;
for(int j = 0; j < width; j++)
if(markIndices[j] != -1)
result.push_back(PInt(markIndices[j], j));
return result;
} |
(
Сообщение от Navovvol
