diff options
Diffstat (limited to 'graph/blossom.cpp')
| -rw-r--r-- | graph/blossom.cpp | 84 |
1 files changed, 84 insertions, 0 deletions
diff --git a/graph/blossom.cpp b/graph/blossom.cpp new file mode 100644 index 0000000..cc19a2b --- /dev/null +++ b/graph/blossom.cpp @@ -0,0 +1,84 @@ +struct GM { + vector<vector<int>> adjlist; + // pairs ist der gematchte knoten oder n + vector<int> pairs, first, que; + vector<pair<int, int>> label; + int head, tail; + + GM(int n) : adjlist(n), pairs(n + 1, n), first(n + 1, n), + que(n), label(n + 1, {-1, -1}) {} + + void rematch(int v, int w) { + int t = pairs[v]; pairs[v] = w; + if (pairs[t] != v) return; + if (label[v].second == -1) { + pairs[t] = label[v].first; + rematch(pairs[t], t); + } else { + int x = label[v].first; + int y = label[v].second; + rematch(x, y); + rematch(y, x); + }} + + int findFirst(int u) { + return label[first[u]].first < 0 ? first[u] + : first[u] = findFirst(first[u]); + } + + void relabel(int x, int y) { + int r = findFirst(x); + int s = findFirst(y); + if (r == s) return; + auto h = label[r] = label[s] = {~x, y}; + int join; + while (true) { + if (s != sz(adjlist)) swap(r, s); + r = findFirst(label[pairs[r]].first); + if (label[r] == h) { + join = r; + break; + } else { + label[r] = h; + }} + for (int v : {first[x], first[y]}) { + for (; v != join; v = first[label[pairs[v]].first]) { + label[v] = {x, y}; + first[v] = join; + que[tail++] = v; + }}} + + bool augment(int u) { + label[u] = {sz(adjlist), -1}; + first[u] = sz(adjlist); + head = tail = 0; + for (que[tail++] = u; head < tail;) { + int x = que[head++]; + for (int y : adjlist[x]) { + if (pairs[y] == sz(adjlist) && y != u) { + pairs[y] = x; + rematch(x, y); + return true; + } else if (label[y].first >= 0) { + relabel(x, y); + } else if (label[pairs[y]].first == -1) { + label[pairs[y]].first = x; + first[pairs[y]] = y; + que[tail++] = pairs[y]; + }}} + return false; + } + + int match() { + int matching = head = tail = 0; + for (int u = 0; u < sz(adjlist); u++) { + if (pairs[u] < sz(adjlist) || !augment(u)) continue; + matching++; + for (int i = 0; i < tail; i++) + label[que[i]] = label[pairs[que[i]]] = {-1, -1}; + label[sz(adjlist)] = {-1, -1}; + } + return matching; + } + +};
\ No newline at end of file |