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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| #include <vector>
#include <limits>
#include <iostream>
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;
}
int main()
{
VVInt matrix;
vector <int> data;
int n, num;
cout << "input number of workers: ";
cin >> n;
cout << "input data " << endl;
for (int l = 0; l < n; l++)
{
for (int i = 0; i < n; i++)
{
cin >> num;
data.push_back(num);
}
matrix.push_back(data);
data.clear();
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++)
cout << " " << matrix[i][j] << " ";
cout << endl;
}
cout << endl;
VPInt result = hungarian(matrix);
int size = result.size();
for (int i = 0; i < size; i++)
cout << "str " << matrix[i][result[i].first] << " " << endl;
system("pause");
} |
(
