diff options
| -rw-r--r-- | graph/maxCarBiMatch.cpp | 18 |
1 files changed, 10 insertions, 8 deletions
diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp index c086abc..be65d78 100644 --- a/graph/maxCarBiMatch.cpp +++ b/graph/maxCarBiMatch.cpp @@ -3,13 +3,11 @@ vector< vector<int> > adjlist; // Gerichtete Kanten, von links nach rechts. vector<int> pairs; // Zu jedem Knoten der gematchte Knoten rechts, oder -1. vector<bool> visited; -bool dfs(int i) { - if (visited[i]) return false; - visited[i] = true; - for (vector<int>::iterator vit = adjlist[i].begin(); vit != adjlist[i].end(); vit++) { - if (pairs[*vit] < 0 || dfs(pairs[*vit])) { - pairs[*vit] = i; pairs[i] = *vit; return true; - } +bool dfs(int v) { + if (visited[v]) return false; + visited[v] = true; + for (auto w : adjlist[v]) if (pairs[w] < 0 || dfs(pairs[w])) { + pairs[w] = v; pairs[v] = w; return true; } return false; } @@ -18,7 +16,11 @@ bool dfs(int i) { int kuhn(int n, int m) { pairs.assign(n + m, -1); int ans = 0; - for (int i = 0; i < n; i++) { + // 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) { visited.assign(n + m, false); ans += dfs(i); } |