From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- graph/maxCarBiMatch.cpp | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'graph/maxCarBiMatch.cpp') diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp index 24aebef..0a38d84 100644 --- a/graph/maxCarBiMatch.cpp +++ b/graph/maxCarBiMatch.cpp @@ -1,5 +1,3 @@ -// Laufzeit: O(n*min(ans^2, |E|)) -// Kanten von links nach rechts. Die ersten n Knoten sind links, die anderen rechts. vector> adjlist; vector pairs; // Der gematchte Knoten oder -1. vector visited; @@ -14,12 +12,12 @@ bool dfs(int v) { } int kuhn(int n) { // n = #Knoten links. - pairs.assign(adjlist.size(), -1); + pairs.assign(sz(adjlist), -1); int ans = 0; // Greedy Matching. Optionale Beschleunigung. for (int i = 0; i < n; i++) for (auto w : adjlist[i]) - if (pairs[w] == -1) { pairs[i] = w; pairs[w] = i; ans++; break; } - for (int i = 0; i < n; i++) if (pairs[i] == -1) { + if (pairs[w] < 0) {pairs[i] = w; pairs[w] = i; ans++; break;} + for (int i = 0; i < n; i++) if (pairs[i] < 0) { visited.assign(n, false); ans += dfs(i); } -- cgit v1.2.3