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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
| #include "stdafx.h"
#include <vector>
#include <limits>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
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(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(){
setlocale(LC_ALL, "RUSSIAN");
//Создаем файловый поток и связываем его с файлом
ifstream in("input.txt");
if (in.is_open())
{
int count = 0;
int temp;
while (!in.eof())
{
in >> temp;
count++;
}
in.seekg(0, ios::beg);
in.clear();
int count_space = 0;
char symbol;
while (!in.eof())
{
in.get(symbol);
if (symbol == ' ') count_space++;
if (symbol == '\n') break;
}
in.seekg(0, ios::beg);
in.clear();
int n = count / (count_space + 1);
int m = count_space + 1;
VVInt x;
//Считаем матрицу из файла
for (int i = 0; i < n; i++){
VInt temp;
for (int j = 0; j < m; j++){
int gro;
in >> gro;
temp.push_back(gro);
}
x.push_back(temp);
}
VPInt zal = hungarian(x); //ошибка возникает тут
in.close();//под конец закроем файла
}
else
{
//Если открытие файла прошло не успешно
cout << "Файл не найден.";
}
system("pause");
return 0;
} |