Алгоритм Куна: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
{|width=100% | |||
|width=50%| | |||
'''Простой вариант''' | |||
bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, vector<int> &pairFromA) { | bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, vector<int> &pairFromA) { | ||
visited[vFromA] = 1; | visited[vFromA] = 1; | ||
| Строка 24: | Строка 28: | ||
return pairFromA; | return pairFromA; | ||
} | } | ||
|width=50%| | |||
'''Более эффективный вариант без обнуления visited''' | |||
bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, {{Changed|int i,}} vector<int> &pairFromA) { | |||
visited[vFromA] = {{Changed|i}}; | |||
for (int vFromB : graphA[vFromA]) { | |||
int &toFromA = pairFromA[vFromB]; | |||
if (toFromA == -1 || {{Changed|1=visited[toFromA] != i}} && dfs(graphA, toFromA, visited, {{Changed|i,}} pairFromA)) { | |||
toFromA = vFromA; | |||
return 1; | |||
} | |||
} | |||
return 0; | |||
} | |||
vector<int> kuhn(vector<vector<int>> &graphA, int vertexCountB) { | |||
{{Changed|1=vector<int> visited(graphA.size(), -1);}} | |||
vector<int> pairFromA(vertexCountB, -1); | |||
for (int vFromA = 0; vFromA < graphA.size(); vFromA++) | |||
dfs(graphA, vFromA, visited, {{Changed|vFromA,}} pairFromA); | |||
return pairFromA; | |||
} | |||
|} | |||
{|width=100% | |||
|width=50%| | |||
vector<int> kuhnWithGreedyInitialization(vector<vector<int>> &graphA, int vertexCountB) { | vector<int> kuhnWithGreedyInitialization(vector<vector<int>> &graphA, int vertexCountB) { | ||
vector<int> | vector<int> greedyVisited(graphA.size()); | ||
vector<int> pairFromA(vertexCountB, -1); | |||
for (int vFromA = 0; vFromA < graphA.size(); vFromA++) { | for (int vFromA = 0; vFromA < graphA.size(); vFromA++) { | ||
for (int vFromB : graphA[vFromA]) { | for (int vFromB : graphA[vFromA]) { | ||
if (pairFromA[vFromB] == -1) { | if (pairFromA[vFromB] == -1) { | ||
greedyVisited[vFromA] = 1; | |||
pairFromA[vFromB] = vFromA; | pairFromA[vFromB] = vFromA; | ||
break; | break; | ||
} | } | ||
| Строка 47: | Строка 83: | ||
return pairFromA; | return pairFromA; | ||
} | } | ||
|width=50%| | |||
vector<int> kuhnWithGreedyInitialization(vector<vector<int>> &graphA, int vertexCountB) { | |||
vector<int> greedyVisited(graphA.size()); | |||
vector<int> pairFromA(vertexCountB, -1); | |||
for (int vFromA = 0; vFromA < graphA.size(); vFromA++) { | |||
for (int vFromB : graphA[vFromA]) { | |||
if (pairFromA[vFromB] == -1) { | |||
greedyVisited[vFromA] = 1; | |||
pairFromA[vFromB] = vFromA; | |||
break; | |||
} | |||
} | |||
} | |||
{{Changed|1=vector<int> visited(graphA.size(), -1);}} | |||
for (int vFromA = 0; vFromA < graphA.size(); vFromA++) | |||
if (!greedyVisited[vFromA]) | |||
dfs(graphA, vFromA, visited, {{Changed|vFromA,}} pairFromA); | |||
return pairFromA; | |||
} | |||
|} | |||
== Ссылки == | == Ссылки == | ||
Текущая версия от 03:16, 25 февраля 2023
|
Простой вариант bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, vector<int> &pairFromA) {
visited[vFromA] = 1;
for (int vFromB : graphA[vFromA]) {
int &toFromA = pairFromA[vFromB];
if (toFromA == -1 || !visited[toFromA] && dfs(graphA, toFromA, visited, pairFromA)) {
toFromA = vFromA;
return 1;
}
}
return 0;
}
vector<int> kuhn(vector<vector<int>> &graphA, int vertexCountB) {
vector<int> pairFromA(vertexCountB, -1);
for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
vector<int> visited(graphA.size());
dfs(graphA, vFromA, visited, pairFromA);
}
return pairFromA;
}
|
Более эффективный вариант без обнуления visited bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, int i, vector<int> &pairFromA) { visited[vFromA] = i; for (int vFromB : graphA[vFromA]) { int &toFromA = pairFromA[vFromB]; if (toFromA == -1 || visited[toFromA] != i && dfs(graphA, toFromA, visited, i, pairFromA)) { toFromA = vFromA; return 1; } } return 0; } vector<int> kuhn(vector<vector<int>> &graphA, int vertexCountB) { vector<int> visited(graphA.size(), -1); vector<int> pairFromA(vertexCountB, -1); for (int vFromA = 0; vFromA < graphA.size(); vFromA++) dfs(graphA, vFromA, visited, vFromA, pairFromA); return pairFromA; } |
vector<int> kuhnWithGreedyInitialization(vector<vector<int>> &graphA, int vertexCountB) {
vector<int> greedyVisited(graphA.size());
vector<int> pairFromA(vertexCountB, -1);
for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
for (int vFromB : graphA[vFromA]) {
if (pairFromA[vFromB] == -1) {
greedyVisited[vFromA] = 1;
pairFromA[vFromB] = vFromA;
break;
}
}
}
for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
if (!greedyVisited[vFromA]) {
vector<int> visited(graphA.size());
dfs(graphA, vFromA, visited, pairFromA);
}
}
return pairFromA;
}
|
vector<int> kuhnWithGreedyInitialization(vector<vector<int>> &graphA, int vertexCountB) {
vector<int> greedyVisited(graphA.size());
vector<int> pairFromA(vertexCountB, -1);
for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
for (int vFromB : graphA[vFromA]) {
if (pairFromA[vFromB] == -1) {
greedyVisited[vFromA] = 1;
pairFromA[vFromB] = vFromA;
break;
}
}
}
vector<int> visited(graphA.size(), -1);
for (int vFromA = 0; vFromA < graphA.size(); vFromA++)
if (!greedyVisited[vFromA])
dfs(graphA, vFromA, visited, vFromA, pairFromA);
return pairFromA;
}
|
Ссылки
Теория:
- e-maxx.ru — Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе
- neerc.ifmo.ru/wiki — Алгоритм Куна для поиска максимального паросочетания
- algorithmica.org — Паросочетания
- Codeforces — Паросочетание. Быстрый Кун
- Brilliant.org — Matching Algorithms
Код: