Алгоритм Куна: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) (Отмена правки 2793, сделанной Ctrlalt (обсуждение)) Метка: отмена |
||
| Строка 24: | Строка 24: | ||
return pairFromA; | return pairFromA; | ||
} | } | ||
== Ссылки == | |||
Теория: | |||
* [http://e-maxx.ru/algo/kuhn_matching e-maxx.ru — Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе] | |||
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%83%D0%BD%D0%B0_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F neerc.ifmo.ru/wiki — Алгоритм Куна для поиска максимального паросочетания] | |||
* [https://algorithmica.org/ru/matching algorithmica.org — Паросочетания] | |||
* [https://codeforces.com/blog/entry/17023 Codeforces — Паросочетание. Быстрый Кун] | |||
* [http://brilliant.org/wiki/matching-algorithms Brilliant.org — Matching Algorithms] | |||
Код: | |||
* [https://github.com/indy256/codelibrary/blob/master/cpp/graphs/matchings/max_bipartite_matching_EV.cpp codelibrary/cpp/graphs/matchings/max_bipartite_matching_EV.cpp] | |||
* [http://github.com/ADJA/algos/blob/master/Graphs/BipartiteMatchingKuhn.cpp algos/Graphs/BipartiteMatchingKuhn.cpp] | |||
Версия от 00:05, 29 сентября 2022
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;
}
Ссылки
Теория:
- e-maxx.ru — Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе
- neerc.ifmo.ru/wiki — Алгоритм Куна для поиска максимального паросочетания
- algorithmica.org — Паросочетания
- Codeforces — Паросочетание. Быстрый Кун
- Brilliant.org — Matching Algorithms
Код: