summaryrefslogtreecommitdiff
path: root/graph
diff options
context:
space:
mode:
Diffstat (limited to 'graph')
-rw-r--r--graph/TSP.cpp4
-rw-r--r--graph/bellmannFord.cpp2
-rw-r--r--graph/bitonicTSPsimple.cpp2
-rw-r--r--graph/blossom.cpp5
-rw-r--r--graph/capacityScaling.cpp2
-rw-r--r--graph/connect.cpp2
-rw-r--r--graph/cycleCounting.cpp12
-rw-r--r--graph/dijkstra.cpp16
-rw-r--r--graph/dinicScaling.cpp6
-rw-r--r--graph/havelHakimi.cpp17
-rw-r--r--graph/hopcroftKarp.cpp4
-rw-r--r--graph/minCostMaxFlow.cpp2
-rw-r--r--graph/pushRelabel2.cpp2
-rw-r--r--graph/pushRelabel3.cpp2
14 files changed, 38 insertions, 40 deletions
diff --git a/graph/TSP.cpp b/graph/TSP.cpp
index 856107f..e0fced6 100644
--- a/graph/TSP.cpp
+++ b/graph/TSP.cpp
@@ -9,9 +9,9 @@ void TSP() {
for (int v = m - 2; v >= 0; v--) {
for (int c = n - 1; c >= 0; c--) {
- for (int g = 0; g < n; g++) {
+ for (int g = 0; g < n; g++) {
if (g != c && !((1 << g) & v)) {
- if ((dp[g][(v | (1 << g))].dist + dist[c][g]) <
+ if ((dp[g][(v | (1 << g))].dist + dist[c][g]) <
dp[c][v].dist) {
dp[c][v].dist =
dp[g][(v | (1 << g))].dist + dist[c][g];
diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp
index 730cad2..785a42d 100644
--- a/graph/bellmannFord.cpp
+++ b/graph/bellmannFord.cpp
@@ -4,7 +4,7 @@ void bellmannFord(int n, vector<edge> edges, int start) {
for (int i = 1; i < n; i++) {
for (edge& e : edges) {
- if (dist[e.from] != INF &&
+ if (dist[e.from] != INF &&
dist[e.from] + e.cost < dist[e.to]) {
dist[e.to] = dist[e.from] + e.cost;
parent[e.to] = e.from;
diff --git a/graph/bitonicTSPsimple.cpp b/graph/bitonicTSPsimple.cpp
index 7a0c3c8..96ae5bd 100644
--- a/graph/bitonicTSPsimple.cpp
+++ b/graph/bitonicTSPsimple.cpp
@@ -11,7 +11,7 @@ double get(int p1, int p2) {
}
void bitonicTour() {
- dp = vector<vector<double>>(sz(dist),
+ dp = vector<vector<double>>(sz(dist),
vector<double>(sz(dist), -1));
get(0, 0);
// return dp[0][0]; // Länger der Tour
diff --git a/graph/blossom.cpp b/graph/blossom.cpp
index 72531c6..13a3246 100644
--- a/graph/blossom.cpp
+++ b/graph/blossom.cpp
@@ -5,7 +5,7 @@ struct GM {
vector<pair<int, int>> label;
int head, tail;
- GM(int n) : adjlist(n), pairs(n + 1, n), first(n + 1, n),
+ 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) {
@@ -15,8 +15,7 @@ struct GM {
pairs[t] = label[v].first;
rematch(pairs[t], t);
} else {
- int x = label[v].first;
- int y = label[v].second;
+ auto [x, y] = label[v];
rematch(x, y);
rematch(y, x);
}}
diff --git a/graph/capacityScaling.cpp b/graph/capacityScaling.cpp
index 8467f81..b8c747f 100644
--- a/graph/capacityScaling.cpp
+++ b/graph/capacityScaling.cpp
@@ -1,5 +1,5 @@
struct edge {
- int from, to;
+ int from, to;
ll f, c;
};
diff --git a/graph/connect.cpp b/graph/connect.cpp
index c38b8bd..b25d844 100644
--- a/graph/connect.cpp
+++ b/graph/connect.cpp
@@ -23,7 +23,7 @@ struct connect {
void eraseEdge(ll id) {
if (connected(edges[id].first, edges[id].second) &&
- lct.query(&lct.nodes[edges[id].first],
+ lct.query(&lct.nodes[edges[id].first],
&lct.nodes[edges[id].second]) == id) {
lct.cut(&lct.nodes[edges[id].first], &lct.nodes[id + n]);
lct.cut(&lct.nodes[edges[id].second], &lct.nodes[id + n]);
diff --git a/graph/cycleCounting.cpp b/graph/cycleCounting.cpp
index c3fe457..bf32874 100644
--- a/graph/cycleCounting.cpp
+++ b/graph/cycleCounting.cpp
@@ -29,11 +29,11 @@ struct cylces {
} else {
seen[c] = true;
paths[c] = cur;
- for (auto e : adj[c]) {
- if (e.first == p) continue;
- cur[e.second].flip();
- findBase(e.first, c, cur);
- cur[e.second].flip();
+ for (auto [to, id] : adj[c]) {
+ if (to == p) continue;
+ cur[id].flip();
+ findBase(to, c, cur);
+ cur[id].flip();
}}}
//cycle must be constrcuted from base
@@ -43,7 +43,7 @@ struct cylces {
for (int i = 0; i < sz(edges); i++) {
if (cur[i]) {
cur[i] = false;
- if (findSet(edges[i].first) ==
+ if (findSet(edges[i].first) ==
findSet(edges[i].second)) break;
unionSets(edges[i].first, edges[i].second);
}}
diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp
index 0b821dd..50c9654 100644
--- a/graph/dijkstra.cpp
+++ b/graph/dijkstra.cpp
@@ -7,15 +7,15 @@ void dijkstra(const vector<vector<path>> &adjlist, int start) {
dist[start] = 0; pq.emplace(0, start);
while (!pq.empty()) {
- path front = pq.top(); pq.pop();
- if (front.first > dist[front.second]) continue; // WICHTIG!
+ auto [dc, c] = pq.top(); pq.pop();
+ if (dc > dist[c]) continue; // WICHTIG!
- for (path e : adjlist[front.second]) {
- ll newDist = front.first + e.first;
- if (newDist < dist[e.second]) {
- dist[e.second] = newDist;
- prev[e.second] = front.second;
- pq.emplace(newDist, e.second);
+ for (auto [dx, x] : adjlist[c]) {
+ ll newDist = dc + dx;
+ if (newDist < dist[x]) {
+ dist[x] = newDist;
+ prev[x] = c;
+ pq.emplace(newDist, x);
}}}
//return dist, prev;
}
diff --git a/graph/dinicScaling.cpp b/graph/dinicScaling.cpp
index 5dc06d6..aecbddc 100644
--- a/graph/dinicScaling.cpp
+++ b/graph/dinicScaling.cpp
@@ -1,5 +1,5 @@
struct edge {
- int from, to;
+ int from, to;
ll f, c;
};
@@ -19,7 +19,7 @@ void addEdge(int from, int to, ll c) {
bool bfs() {
dist.assign(sz(dist), -1);
- dist[t] = sz(adjlist) + 1;
+ dist[t] = sz(adjlist) + 1;
q.push(t);
while (!q.empty() && dist[s] < 0) {
int cur = q.front(); q.pop();
@@ -39,7 +39,7 @@ bool dfs(int v, ll flow) {
if (v == t) return true;
for (; pt[v] < sz(adjlist[v]); pt[v]++) {
int id = adjlist[v][pt[v]], to = edges[id].to;
- if (dist[to] == dist[v] + 1 &&
+ if (dist[to] == dist[v] + 1 &&
edges[id].c - edges[id].f >= flow) {
if (dfs(to, flow)) {
edges[id].f += flow;
diff --git a/graph/havelHakimi.cpp b/graph/havelHakimi.cpp
index 135c4b0..8d5d6ab 100644
--- a/graph/havelHakimi.cpp
+++ b/graph/havelHakimi.cpp
@@ -3,17 +3,16 @@ vector<vector<int>> havelHakimi(const vector<int>& deg) {
for (int i = 0; i < sz(deg); i++) pq.push({deg[i], i});
vector<vector<int>> adj;
while (!pq.empty()) {
- auto v = pq.top(); pq.pop();
- if (sz(pq) < v.first) return {}; //impossible
+ auto [degV, v] = pq.top(); pq.pop();
+ if (sz(pq) < degV) return {}; //impossible
vector<pair<int, int>> todo;
- for (int i = 0; i < v.first; i++) {
- auto u = pq.top(); pq.pop();
- adj[v.second].push_back(u.second);
- adj[u.second].push_back(v.second);
- u.first--;
- if (u.first > 0) todo.push_back(u);
+ for (int i = 0; i < degV; i++) {
+ auto [degU, v] = pq.top(); pq.pop();
+ adj[v].push_back(u);
+ adj[u].push_back(v);
+ if (degU > 1) todo.push_back({degU - 1, u});
}
for (auto e : todo) pq.push(e);
}
return adj;
-}
+}
diff --git a/graph/hopcroftKarp.cpp b/graph/hopcroftKarp.cpp
index c0eda96..09d27bc 100644
--- a/graph/hopcroftKarp.cpp
+++ b/graph/hopcroftKarp.cpp
@@ -22,8 +22,8 @@ bool bfs(int n) {
bool dfs(int u) {
for (int v : adjlist[u]) {
if (pairs[v] < 0 ||
- (dist[pairs[v]] > dist[u] && dfs(pairs[v]))) {
- pairs[v] = u; pairs[u] = v;
+ (dist[pairs[v]] > dist[u] && dfs(pairs[v]))) {
+ pairs[v] = u; pairs[u] = v;
return true;
}}
dist[u] = -1;
diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp
index 46d444c..27f6b34 100644
--- a/graph/minCostMaxFlow.cpp
+++ b/graph/minCostMaxFlow.cpp
@@ -12,7 +12,7 @@ struct MinCostFlow {
const int s, t;
ll maxflow, mincost;
- MinCostFlow(int n, int source, int target) :
+ MinCostFlow(int n, int source, int target) :
adjlist(n), s(source), t(target) {};
void addedge(int u, int v, ll c, ll cost) {
diff --git a/graph/pushRelabel2.cpp b/graph/pushRelabel2.cpp
index f4a66e8..b8ec3e9 100644
--- a/graph/pushRelabel2.cpp
+++ b/graph/pushRelabel2.cpp
@@ -1,7 +1,7 @@
constexpr ll inf = 1ll<<60;
struct edge {
- int from, to;
+ int from, to;
ll f, c;
};
diff --git a/graph/pushRelabel3.cpp b/graph/pushRelabel3.cpp
index bdbe0a5..1a0af81 100644
--- a/graph/pushRelabel3.cpp
+++ b/graph/pushRelabel3.cpp
@@ -1,5 +1,5 @@
struct edge {
- int from, to;
+ int from, to;
ll f, c;
};
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 21:46:00 +0000