From 8d11c6c8213f46f0fa19826917c255edd5d43cb1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 28 Jul 2024 22:54:40 +0200 Subject: Test (#4) * update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? * better fix * fix virtual tree * more tests * more tests * recursive closest pair * more tests * decrease limit * new tests * more tests * fix name * more tests * add test * new test * more tests * more tests * more tests * more tests * new test and content * new code * new code * larger tests * fix and test * new test * new test * update pdf * remove comments * new test * more tests * more testcases * more tests * increased limit * more tests * more tests * more tests * new tests * more tests * shortened code * new test * add basic tests for bigint * more tests * removed old files * new test * ignore some files * more auto more ccw * fix test * more tests * fix * new tests * more tests * more tests * stronger test * actually verify delaunay... * more tests * fix header * more tests * run tests parallel? * test parralel? * add --missing * separate workflows * test * is the pdf checked? * separate workflows * fix workflow * more workflows --------- Co-authored-by: Yidi --- content/graph/blossom.cpp | 82 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 82 insertions(+) create mode 100644 content/graph/blossom.cpp (limited to 'content/graph/blossom.cpp') diff --git a/content/graph/blossom.cpp b/content/graph/blossom.cpp new file mode 100644 index 0000000..7bd494a --- /dev/null +++ b/content/graph/blossom.cpp @@ -0,0 +1,82 @@ +struct GM { + vector> adj; + // pairs ist der gematchte knoten oder n + vector pairs, first, que; + vector> label; + int head, tail; + + GM(int n) : adj(n), pairs(n + 1, n), first(n + 1, n), + que(n), label(n + 1, {-1, -1}) {} + + void rematch(int u, int v) { + int t = pairs[u]; pairs[u] = v; + if (pairs[t] != u) return; + if (label[u].second == -1) { + pairs[t] = label[u].first; + rematch(pairs[t], t); + } else { + auto [x, y] = label[u]; + rematch(x, y); + rematch(y, x); + }} + + int findFirst(int v) { + return label[first[v]].first < 0 ? first[v] + : first[v] = findFirst(first[v]); + } + + 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(adj)) 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 v) { + label[v] = {sz(adj), -1}; + first[v] = sz(adj); + head = tail = 0; + for (que[tail++] = v; head < tail;) { + int x = que[head++]; + for (int y : adj[x]) { + if (pairs[y] == sz(adj) && y != v) { + 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 v = 0; v < sz(adj); v++) { + if (pairs[v] < sz(adj) || !augment(v)) continue; + matching++; + for (int i = 0; i < tail; i++) + label[que[i]] = label[pairs[que[i]]] = {-1, -1}; + label[sz(adj)] = {-1, -1}; + } + return matching; + } +}; -- cgit v1.2.3