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 --- graph/blossom.cpp | 82 ------------------------------------------------------- 1 file changed, 82 deletions(-) delete mode 100644 graph/blossom.cpp (limited to 'graph/blossom.cpp') diff --git a/graph/blossom.cpp b/graph/blossom.cpp deleted file mode 100644 index 7bd494a..0000000 --- a/graph/blossom.cpp +++ /dev/null @@ -1,82 +0,0 @@ -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