summaryrefslogtreecommitdiff
path: root/content/graph
diff options
context:
space:
mode:
Diffstat (limited to 'content/graph')
-rw-r--r--content/graph/bitonicTSP.cpp2
-rw-r--r--content/graph/bitonicTSPsimple.cpp2
-rw-r--r--content/graph/connect.cpp2
-rw-r--r--content/graph/dinic.cpp55
-rw-r--r--content/graph/dinicScaling.cpp21
-rw-r--r--content/graph/pushRelabel.cpp2
-rw-r--r--content/graph/reroot.cpp86
-rw-r--r--content/graph/scc.cpp19
-rw-r--r--content/graph/virtualTree.cpp6
9 files changed, 121 insertions, 74 deletions
diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp
index 6470232..eee5082 100644
--- a/content/graph/bitonicTSP.cpp
+++ b/content/graph/bitonicTSP.cpp
@@ -27,5 +27,5 @@ auto bitonicTSP() {
(lt.back() == 1 ? lt : ut).push_back(0);
reverse(all(lt));
lt.insert(lt.end(), all(ut));
- return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+ return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position.
}
diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp
index 8b6e6c5..cacfb9c 100644
--- a/content/graph/bitonicTSPsimple.cpp
+++ b/content/graph/bitonicTSPsimple.cpp
@@ -23,5 +23,5 @@ auto bitonicTSP() {
rl.push_back(v); p2 = v;
}}
lr.insert(lr.end(), rl.rbegin(), rl.rend());
- return lr;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+ return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position.
}
diff --git a/content/graph/connect.cpp b/content/graph/connect.cpp
index ffcd6c2..7940b37 100644
--- a/content/graph/connect.cpp
+++ b/content/graph/connect.cpp
@@ -10,7 +10,7 @@ struct connect {
}
void addEdge(int u, int v, int id) {
- lct.nodes[id + n] = LCT::Node(id + n, id + n);
+ lct.nodes[id + n] = LCT::Node(id + n, id);
edges[id] = {u, v};
if (connected(u, v)) {
int old = lct.query(&lct.nodes[u], &lct.nodes[v]);
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/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp
index f4e833a..0974b78 100644
--- a/content/graph/dinicScaling.cpp
+++ b/content/graph/dinicScaling.cpp
@@ -26,17 +26,18 @@ bool bfs(ll lim) {
return dist[t] >= 0;
}
-bool dfs(int v, ll flow) {
- if (v == t) return true;
+ll dfs(int v, ll flow) {
+ 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;
- if (e.c - e.f >= flow && dfs(e.to, flow)) {
- e.f += flow;
- adj[e.to][e.rev].f -= flow;
- return true;
+ 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 false;
+ return 0;
}
ll maxFlow(int source, int target) {
@@ -45,7 +46,11 @@ ll maxFlow(int source, int target) {
for (ll lim = (1LL << 62); lim >= 1; lim /= 2) {
while (bfs(lim)) {
pt.assign(sz(adj), 0);
- while (dfs(s, lim)) flow += lim;
+ ll cur;
+ do {
+ cur = dfs(s, lim);
+ flow += cur;
+ } while (cur > 0);
}}
return flow;
}
diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp
index 73a9eae..ec36026 100644
--- a/content/graph/pushRelabel.cpp
+++ b/content/graph/pushRelabel.cpp
@@ -29,7 +29,7 @@ ll maxFlow(int s, int t) {
cur.assign(n, 0);
H.assign(n, 0);
H[s] = n;
- ec[t] = 1;//never set t to active...
+ ec[t] = 1; //never set t to active...
vector<int> co(2*n);
co[0] = n - 1;
for (Edge& e : adj[s]) addFlow(e, e.c);
diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp
index 4c6a748..379c839 100644
--- a/content/graph/reroot.cpp
+++ b/content/graph/reroot.cpp
@@ -1,62 +1,48 @@
-// Usual Tree DP can be broken down in 4 steps:
-// - Initialize dp[v] = identity
-// - Iterate over all children w and take a value for w
-// by looking at dp[w] and possibly the edge label of v -> w
-// - combine the values of those children
-// usually this operation should be commutative and associative
-// - finalize the dp[v] after iterating over all children
+using W = ll; // edge weight type
+vector<vector<pair<int, W>>> adj;
+
struct Reroot {
- using T = ll;
+ using T = ll; // dp type
- // identity element
- T E() {}
- // x: dp value of child
- // e: index of edge going to child
- T takeChild(T x, int e) {}
- T comb(T x, T y) {}
- // called after combining all dp values of children
- T fin(T x, int v) {}
+ static constexpr T E = 0; // neutral element
+ T takeChild(int v, int c, W w, T x) {} // move child along edge
+ static T comb(T x, T y) {}
+ T fin(int v, T x) {} // add v to own dp value x
- vector<vector<pair<int, int>>> g;
- vector<int> ord, pae;
vector<T> dp;
- T dfs(int v) {
- ord.push_back(v);
- for (auto [w, e] : g[v]) {
- g[w].erase(find(all(g[w]), pair(v, e^1)));
- pae[w] = e^1;
- dp[v] = comb(dp[v], takeChild(dfs(w), e));
+ T dfs0(int v, int from = -1) {
+ T val = E;
+ for (auto [u, w] : adj[v]) {
+ if (u == from) continue;
+ val = comb(val, takeChild(v, u, w, dfs0(u, v)));
}
- return dp[v] = fin(dp[v], v);
+ return dp[v] = fin(v, val);
}
- vector<T> solve(int n, vector<pair<int, int>> edges) {
- g.resize(n);
- for (int i = 0; i < n-1; i++) {
- g[edges[i].first].emplace_back(edges[i].second, 2*i);
- g[edges[i].second].emplace_back(edges[i].first, 2*i+1);
+ void dfs1(int v, int from = -1) {
+ vector<T> pref = {E};
+ for (auto [u, w] : adj[v]) {
+ pref.push_back(takeChild(v, u, w, dp[u]));
}
- pae.assign(n, -1);
- dp.assign(n, E());
- dfs(0);
- vector<T> updp(n, E()), res(n, E());
- for (int v : ord) {
- vector<T> pref(sz(g[v])+1), suff(sz(g[v])+1);
- if (v != 0) pref[0] = takeChild(updp[v], pae[v]);
- for (int i = 0; i < sz(g[v]); i++){
- auto [u, w] = g[v][i];
- pref[i+1] = suff[i] = takeChild(dp[u], w);
- pref[i+1] = comb(pref[i], pref[i+1]);
- }
- for (int i = sz(g[v])-1; i >= 0; i--) {
- suff[i] = comb(suff[i], suff[i+1]);
- }
- for (int i = 0; i < sz(g[v]); i++) {
- updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v);
- }
- res[v] = fin(pref.back(), v);
+ auto suf = pref;
+ partial_sum(all(pref), pref.begin(), comb);
+ exclusive_scan(suf.rbegin(), suf.rend(),
+ suf.rbegin(), E, comb);
+
+ for (int i = 0; i < sz(adj[v]); i++) {
+ auto [u, w] = adj[v][i];
+ if (u == from) continue;
+ dp[v] = fin(v, comb(pref[i], suf[i + 1]));
+ dfs1(u, v);
}
- return res;
+ dp[v] = fin(v, suf[0]);
+ }
+
+ auto solve() {
+ dp.assign(sz(adj), E);
+ dfs0(0);
+ dfs1(0);
+ return dp;
}
};
diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp
index ac9a40b..32f1099 100644
--- a/content/graph/scc.cpp
+++ b/content/graph/scc.cpp
@@ -1,11 +1,12 @@
-vector<vector<int>> adj, sccs;
-int counter;
+vector<vector<int>> adj;
+int counter, sccCounter;
vector<bool> inStack;
vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten.
void visit(int v) {
int old = low[v] = counter++;
- s.push_back(v); inStack[v] = true;
+ s.push_back(v);
+ inStack[v] = true;
for (auto u : adj[v]) {
if (low[u] < 0) visit(u);
@@ -13,20 +14,20 @@ void visit(int v) {
}
if (old == low[v]) {
- sccs.push_back({});
+ sccCounter++;
for (int u = -1; u != v;) {
- u = s.back(); s.pop_back(); inStack[u] = false;
- idx[u] = sz(sccs) - 1;
- sccs.back().push_back(u);
+ u = s.back();
+ s.pop_back();
+ inStack[u] = false;
+ idx[u] = sccCounter - 1;
}}}
void scc() {
inStack.assign(sz(adj), false);
low.assign(sz(adj), -1);
idx.assign(sz(adj), -1);
- sccs.clear();
- counter = 0;
+ counter = sccCounter = 0;
for (int i = 0; i < sz(adj); i++) {
if (low[i] < 0) visit(i);
}}
diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp
index 27d2d6c..6233b27 100644
--- a/content/graph/virtualTree.cpp
+++ b/content/graph/virtualTree.cpp
@@ -3,13 +3,13 @@ vector<int> in, out;
void virtualTree(vector<int> ind) { // indices of used nodes
sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
- for (int i = 0, n = sz(ind); i < n - 1; i++) {
- ind.push_back(lca(ind[i], ind[i + 1]));
+ for (int i = 1, n = sz(ind); i < n; i++) {
+ ind.push_back(lca(ind[i - 1], ind[i]));
}
sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
ind.erase(unique(all(ind)), ind.end());
- int n = ind.size();
+ int n = sz(ind);
vector<vector<int>> tree(n);
vector<int> st = {0};
for (int i = 1; i < n; i++) {
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 16:36:52 +0000