diff options
Diffstat (limited to 'graph/maxCarBiMatch.cpp')
| -rw-r--r-- | graph/maxCarBiMatch.cpp | 12 |
1 files changed, 6 insertions, 6 deletions
diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp index 588568b..0c5ac43 100644 --- a/graph/maxCarBiMatch.cpp +++ b/graph/maxCarBiMatch.cpp @@ -5,8 +5,8 @@ vector<bool> visited; bool dfs(int v) { if (visited[v]) return false; visited[v] = true; - for (auto w : adj[v]) if (pairs[w] < 0 || dfs(pairs[w])) { - pairs[w] = v; pairs[v] = w; return true; + for (int u : adj[v]) if (pairs[u] < 0 || dfs(pairs[u])) { + pairs[u] = v; pairs[v] = u; return true; } return false; } @@ -15,11 +15,11 @@ int kuhn(int n) { // n = #Knoten links. pairs.assign(sz(adj), -1); int ans = 0; // Greedy Matching. Optionale Beschleunigung. - for (int i = 0; i < n; i++) for (auto w : adj[i]) - if (pairs[w] < 0) {pairs[i] = w; pairs[w] = i; ans++; break;} - for (int i = 0; i < n; i++) if (pairs[i] < 0) { + for (int v = 0; v < l; v++) for (int u : adj[v]) + if (pairs[u] < 0) {pairs[u] = v; pairs[v] = u; ans++; break;} + for (int v = 0; v < n; v++) if (pairs[v] < 0) { visited.assign(n, false); - ans += dfs(i); + ans += dfs(v); } return ans; // Größe des Matchings. } |