blob: 7c0fec5b3d12c9d83d7f8925c7f1cfe55db13020 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
vector<vector<int>> adj;
// pairs ist der gematchte Knoten oder -1
vector<int> pairs, dist, ptr;
bool bfs(int l) {
queue<int> q;
for(int v = 0; v < l; v++) {
if (pairs[v] < 0) { dist[v] = 0; q.push(v); }
else dist[v] = -1;
}
bool exist = false;
while(!q.empty()) {
int v = q.front(); q.pop();
for (int u : adj[v]) {
if (pairs[u] < 0) { exist = true; continue; }
if (dist[pairs[u]] < 0) {
dist[pairs[u]] = dist[v] + 1;
q.push(pairs[u]);
}}}
return exist;
}
bool dfs(int v) {
for (; ptr[v] < sz(adj[v]); ptr[v]++) {
int u = adj[v][ptr[v]];
if (pairs[u] < 0 ||
(dist[pairs[u]] > dist[v] && dfs(pairs[u]))) {
pairs[u] = v; pairs[v] = u;
return true;
}}
return false;
}
int hopcroft_karp(int l) { // l = #Knoten links
int ans = 0;
pairs.assign(sz(adj), -1);
dist.resize(l);
// Greedy Matching, optionale Beschleunigung.
for (int v = 0; v < l; v++) for (int u : adj[v])
if (pairs[u] < 0) {pairs[u] = v; pairs[v] = u; ans++; break;}
while(bfs(l)) {
ptr.assign(l, 0);
for(int v = 0; v < l; v++) {
if (pairs[v] < 0) ans += dfs(v);
}}
return ans;
}
|
