Алгоритм Куна - История изменений

Ctrlalt в 03:16, 25 февраля 2023

2023-02-25T03:16:01Z

@@ Строка 1: / Строка 1: @@
   bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, vector<int> &pairFromA) {
       visited[vFromA] = 1;
@@ Строка 24: / Строка 28: @@
       return pairFromA;
+  }
   vector<int> kuhnWithGreedyInitialization(vector<vector<int>> &graphA, int vertexCountB) {
-      vector<int> pairFromA(vertexCountB, -1), greedyVisited(graphA.size());
+      vector<int> greedyVisited(graphA.size());
       for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
           for (int vFromB : graphA[vFromA]) {
               if (pairFromA[vFromB] == -1) {
                   pairFromA[vFromB] = vFromA;
                   break;
+              }
@@ Строка 47: / Строка 83: @@
       return pairFromA;
+  }
 == Ссылки ==

Ctrlalt в 01:02, 29 сентября 2022

2022-09-29T01:02:36Z

@@ Строка 20: / Строка 20: @@
           vector<int> visited(graphA.size());
           dfs(graphA, vFromA, visited, pairFromA);
+      }

Ctrlalt: Отмена правки 2793, сделанной Ctrlalt (обсуждение)

2022-09-29T00:05:12Z

Отмена правки 2793, сделанной Ctrlalt (обсуждение)

← Предыдущая версия		Версия от 00:05, 29 сентября 2022
Строка 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]

Ctrlalt в 00:04, 29 сентября 2022

2022-09-29T00:04:53Z

← Предыдущая версия		Версия от 00:04, 29 сентября 2022
Строка 1:		Строка 1:
	vector<vector<int>> g;		bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, vector<int> &pairFromA) {
	vector<int> ~~pairFromA;~~		visited[vFromA] = 1;
	vector<int> visited;

	~~bool dfs(int vFromA) {~~		for (int vFromB : graphA[vFromA]) {
	~~visited[vFromA] = 1;~~		int &toFromA = pairFromA[vFromB];
	for (int vFromB : g[vFromA]) {
	int &to = pairFromA[vFromB];		if (toFromA == -1 \|\| !visited[toFromA] && dfs(graphA, toFromA, visited, pairFromA)) {
	if (to == -1 \|\| !visited[to] && dfs(to)) {		toFromA = vFromA;
	to = vFromA;
	return 1;		return 1;
	}		}
	}		}

	return 0;		return 0;
	}		}

	~~void~~ kuhn(int ~~aSize~~, int ~~bSize~~) {		vector<int> kuhn(vector<vector<int>> &graphA, int vertexCountB) {
	pairFromA~~.assign~~(~~bSize~~, -1);		vector<int> pairFromA(vertexCountB, -1);
	for (int vFromA = 0; vFromA < ~~aSize~~; vFromA++) {
	visited.~~assign~~(~~aSize, 0~~);		for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
	dfs(vFromA);		vector<int> visited(graphA.size());
			dfs(graphA, vFromA, visited, 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]

Ctrlalt в 20:55, 24 сентября 2020

2020-09-24T20:55:54Z

@@ Строка 1: / Строка 1: @@
 == Ссылки ==
-* [http://e-maxx.ru/algo/kuhn_matching e-maxx.ru &mdash; Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе]
+Теория:
-* [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 &mdash; Алгоритм Куна для поиска максимального паросочетания]
+* [http://e-maxx.ru/algo/kuhn_matching e-maxx.ru — Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе]
 * [http://brilliant.org/wiki/matching-algorithms Brilliant.org — Matching Algorithms]
-* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxMatching.java CodeLibrary &mdash; Maximum matching for bipartite graph. Kuhn's algorithm in O(V^3)]
+Код:
-* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxMatching2.java CodeLibrary &mdash; Maximum matching for bipartite graph. Kuhn's algorithm in O(EV)]
+* [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 &mdash; Kuhn algorithm for maximum matching in bipartite graph]
+* [http://github.com/ADJA/algos/blob/master/Graphs/BipartiteMatchingKuhn.cpp algos/Graphs/BipartiteMatchingKuhn.cpp]

Ctrlalt: /* Ссылки */

2020-01-02T18:46:28Z

Ссылки

← Предыдущая версия		Версия от 18:46, 2 января 2020
Строка 2:		Строка 2:
	* [http://e-maxx.ru/algo/kuhn_matching e-maxx.ru — Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе]		* [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 — Алгоритм Куна для поиска максимального паросочетания]		* [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 — Алгоритм Куна для поиска максимального паросочетания]
			* [http://brilliant.org/wiki/matching-algorithms Brilliant.org — Matching Algorithms]
	* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxMatching.java CodeLibrary — Maximum matching for bipartite graph. Kuhn's algorithm in O(V^3)]		* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxMatching.java CodeLibrary — Maximum matching for bipartite graph. Kuhn's algorithm in O(V^3)]
	* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxMatching2.java CodeLibrary — Maximum matching for bipartite graph. Kuhn's algorithm in O(EV)]		* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxMatching2.java CodeLibrary — Maximum matching for bipartite graph. Kuhn's algorithm in O(EV)]
	* [http://github.com/ADJA/algos/blob/master/Graphs/BipartiteMatchingKuhn.cpp Algos — Kuhn algorithm for maximum matching in bipartite graph]		* [http://github.com/ADJA/algos/blob/master/Graphs/BipartiteMatchingKuhn.cpp Algos — Kuhn algorithm for maximum matching in bipartite graph]

Ctrlalt: Новая страница: «== Ссылки == * [http://e-maxx.ru/algo/kuhn_matching e-maxx.ru — Алгоритм Куна нахождения наибольшего паросоче…»

2015-01-30T20:03:19Z

Новая страница: «== Ссылки == * [http://e-maxx.ru/algo/kuhn_matching e-maxx.ru — Алгоритм Куна нахождения наибольшего паросоче…»

Новая страница

== Ссылки ==
* [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 — Алгоритм Куна для поиска максимального паросочетания]
* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxMatching.java CodeLibrary — Maximum matching for bipartite graph. Kuhn's algorithm in O(V^3)]
* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxMatching2.java CodeLibrary — Maximum matching for bipartite graph. Kuhn's algorithm in O(EV)]
* [http://github.com/ADJA/algos/blob/master/Graphs/BipartiteMatchingKuhn.cpp Algos — Kuhn algorithm for maximum matching in bipartite graph]