diff options
| -rw-r--r-- | content/geometry/segmentIntersection.cpp | 2 | ||||
| -rw-r--r-- | content/graph/dinic.cpp | 55 | ||||
| -rw-r--r-- | content/string/duval.cpp | 8 | ||||
| -rw-r--r-- | tcr.pdf | bin | 691111 -> 691029 bytes | |||
| -rw-r--r-- | test/graph/dinic.cpp | 62 |
5 files changed, 121 insertions, 6 deletions
diff --git a/content/geometry/segmentIntersection.cpp b/content/geometry/segmentIntersection.cpp index acce7cc..afc01b2 100644 --- a/content/geometry/segmentIntersection.cpp +++ b/content/geometry/segmentIntersection.cpp @@ -29,7 +29,7 @@ bool lessPT(const pt& a, const pt& b) { } bool intersect(const seg& a, const seg& b) { - return lineSegmentIntersection(a.a, a.b, b.a, b.b); + return segmentIntersection(a.a, a.b, b.a, b.b); //@\sourceref{geometry/linesAndSegments.cpp}@ } pair<int, int> intersect(vector<seg>& segs) { diff --git a/content/graph/dinic.cpp b/content/graph/dinic.cpp new file mode 100644 index 0000000..2e58a2d --- /dev/null +++ b/content/graph/dinic.cpp @@ -0,0 +1,55 @@ +struct Edge { + int to, rev; + ll f, c; +}; + +vector<vector<Edge>> adj; +int s, t; +vector<int> pt, dist; + +void addEdge(int u, int v, ll c) { + adj[u].push_back({v, (int)sz(adj[v]), 0, c}); + adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0}); +} + +bool bfs() { + dist.assign(sz(adj), -1); + dist[s] = 0; + queue<int> q({s}); + while (!q.empty() && dist[t] < 0) { + int v = q.front(); q.pop(); + for (Edge& e : adj[v]) { + if (dist[e.to] < 0 && e.c - e.f > 0) { + dist[e.to] = dist[v] + 1; + q.push(e.to); + }}} + return dist[t] >= 0; +} + +ll dfs(int v, ll flow = INF) { + if (v == t || flow == 0) return flow; + for (; pt[v] < sz(adj[v]); pt[v]++) { + Edge& e = adj[v][pt[v]]; + if (dist[e.to] != dist[v] + 1) continue; + ll cur = dfs(e.to, min(e.c - e.f, flow)); + if (cur > 0) { + e.f += cur; + adj[e.to][e.rev].f -= cur; + return cur; + }} + return 0; +} + +ll maxFlow(int source, int target) { + s = source, t = target; + ll flow = 0; + while (bfs()) { + pt.assign(sz(adj), 0); + ll cur; + do { + cur = dfs(s); + flow += cur; + } while (cur > 0); + } + return flow; +} diff --git a/content/string/duval.cpp b/content/string/duval.cpp index bf36cce..253bae1 100644 --- a/content/string/duval.cpp +++ b/content/string/duval.cpp @@ -6,9 +6,8 @@ vector<pair<int, int>> duval(const string& s) { if (s[k] < s[j]) k = i; else k++; } - while (i <= k) { + for (; i <= k; i += j - k) { res.push_back({i, i + j - k}); - i += j - k; }} return res; } @@ -16,6 +15,5 @@ vector<pair<int, int>> duval(const string& s) { int minrotation(const string& s) { auto parts = duval(s+s); for (auto [l, r] : parts) { - if (l < sz(s) && r >= sz(s)) { - return l; -}}} + if (r >= sz(s)) return l; +}} Binary files differdiff --git a/test/graph/dinic.cpp b/test/graph/dinic.cpp new file mode 100644 index 0000000..5af7c6f --- /dev/null +++ b/test/graph/dinic.cpp @@ -0,0 +1,62 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +namespace dinic { +#include <graph/dinic.cpp> +} + +namespace pushRelabel { +#include <graph/pushRelabel.cpp> +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + int n = Random::integer<int>(2, 30); + int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1))); + + dinic::adj.assign(n, {}); + pushRelabel::adj.assign(n, {}); + + Graph<NoData, true> g(n); + g.erdosRenyi(m); + g.forEdges([](int a, int b){ + ll w = Random::integer<ll>(1, 1'000'000'000'000ll); + dinic::addEdge(a, b, w); + pushRelabel::addEdge(a, b, w); + }); + + ll got = dinic::maxFlow(0, n - 1); + ll expected = pushRelabel::maxFlow(0, n - 1); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 50000; +constexpr int M = 200000; +void performance_test() { + using namespace dinic; + timer t; + Graph<NoData> g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([](int a, int b){ + ll w1 = Random::integer<ll>(1, 1'000'000'000'000ll); + ll w2 = Random::integer<ll>(1, 1'000'000'000'000ll); + addEdge(a, b, w1); + addEdge(b, a, w2); + }); + + t.start(); + hash_t hash = maxFlow(0, N - 1); + t.stop(); + if (t.time > 2000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} |