diff options
| -rw-r--r-- | graph/maxCarBiMatch.cpp | 18 | ||||
| -rw-r--r-- | tcr.pdf | bin | 261970 -> 260895 bytes |
2 files changed, 8 insertions, 10 deletions
diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp index be65d78..a6a242f 100644 --- a/graph/maxCarBiMatch.cpp +++ b/graph/maxCarBiMatch.cpp @@ -1,6 +1,6 @@ -// Laufzeit: O(n*(|V|+|E|)) -vector< vector<int> > adjlist; // Gerichtete Kanten, von links nach rechts. -vector<int> pairs; // Zu jedem Knoten der gematchte Knoten rechts, oder -1. +// Laufzeit: O(n*min(ans^2, |E|)) +vector< vector<int> > adjlist; // Von links nach rechts. +vector<int> pairs; // Der gematchte Knoten oder -1. vector<bool> visited; bool dfs(int v) { @@ -12,16 +12,14 @@ bool dfs(int v) { return false; } -// n = #Knoten links (0..n-1), m = #Knoten rechts -int kuhn(int n, int m) { - pairs.assign(n + m, -1); +int kuhn(int n) { // n = #Knoten links. + pairs.assign(adjlist.size(), -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++) 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) { - visited.assign(n + m, false); + visited.assign(n, false); ans += dfs(i); } return ans; // Größe des Matchings. Binary files differ |