summaryrefslogtreecommitdiff
path: root/graph
diff options
context:
space:
mode:
Diffstat (limited to 'graph')
-rw-r--r--graph/LCA.cpp21
-rw-r--r--graph/articulationPoints.cpp2
-rw-r--r--graph/bitonicTSP.cpp34
-rw-r--r--graph/graph.tex50
-rw-r--r--graph/kruskal.cpp9
-rw-r--r--graph/lca.cpp28
-rw-r--r--graph/matching.cpp35
-rw-r--r--graph/maxCarBiMatch.cpp2
-rw-r--r--graph/maxWeightBipartiteMatching.cpp54
9 files changed, 162 insertions, 73 deletions
diff --git a/graph/LCA.cpp b/graph/LCA.cpp
deleted file mode 100644
index c79cc5c..0000000
--- a/graph/LCA.cpp
+++ /dev/null
@@ -1,21 +0,0 @@
-vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N);
-vector<vector<int>> graph(MAX_N);
-
-// Funktioniert nur mit von der Wurzel weggerichteten Kanten.
-// Falls ungerichtete Kanten, visited-check einführen.
-void initLCA(int gi, int d, int &c) { // Laufzeit: O(n)
- visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++;
- for(int gn : graph[gi]) {
- initLCA(gn, d+1, c);
- visited[c] = gi, depth[c] = d, c++;
-}}
-
-int getLCA(int a, int b) { // Laufzeit: O(1)
- return visited[queryRMQ(
- min(first[a], first[b]), max(first[a], first[b]))];
-}
-
-// Benutzung:
-int c = 0;
-initLCA(0, 0, c);
-initRMQ(); // Ersetze das data im RMQ-Code von oben durch depth.
diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp
index e7139d0..fba08bb 100644
--- a/graph/articulationPoints.cpp
+++ b/graph/articulationPoints.cpp
@@ -23,7 +23,7 @@ void findArticulationPoints() {
counter = 0;
low.resize(adjlist.size());
d.assign(adjlist.size(), 0);
- isArtPoint.assign(adjlist.size(), false);
+ isArt.assign(adjlist.size(), false);
bridges.clear(); //nur fuer Bruecken
for (int v = 0; v < (int)adjlist.size(); v++) {
if (!d[v]) {
diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp
index 9e4fac1..2a8b5f9 100644
--- a/graph/bitonicTSP.cpp
+++ b/graph/bitonicTSP.cpp
@@ -1,26 +1,24 @@
// Laufzeit: O(n^2)
-vector<vector<double>> dist; // Initialisiere mit Entfernungen zwischen Punkten.
-vector<vector<double>> dp;
+vector<vector<double>> dp, dist; // Entfernungen zwischen Punkten.
double get(int p1, int p2) {
- int v = max(p1, p2) + 1;
- if (v == dist.size()) return dist[p1][v - 1] + dist[p2][v - 1];
- if (dp[p1][p2] >= 0.0) return dp[p1][p2];
- double tryLR = dist[p1][v] + get(v, p2), tryRL = dist[p2][v] + get(p1, v);
- return dp[p1][p2] = min(tryLR, tryRL);
+ int v = max(p1, p2) + 1;
+ if (v == dist.size()) return dist[p1][v - 1] + dist[p2][v - 1];
+ if (dp[p1][p2] >= 0.0) return dp[p1][p2];
+ double tryLR = dist[p1][v] + get(v, p2);
+ double tryRL = dist[p2][v] + get(p1, v);
+ return dp[p1][p2] = min(tryLR, tryRL);
}
void bitonicTour() {
- dp = vector<vector<double>>(dist.size(), vector<double>(dist.size(), -1));
- get(0, 0);
- // return dp[0][0]; // Länger der Tour
- vector<int> lr = {0}, rl = {0};
- for (int p1 = 0, p2 = 0, v; (v = max(p1, p2) + 1) < dist.size();) {
- if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) {
- lr.push_back(v); p1 = v;
- } else {
- rl.push_back(v); p2 = v;
+ dp.assign(dist.size(), vector<double>(dist.size(), -1));
+ get(0, 0); // return dp[0][0]; // Länger der Tour
+ vector<int> lr = {0}, rl = {0};
+ for (int p1 = 0, p2 = 0, v; (v = max(p1, p2) + 1) < dist.size();) {
+ if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) {
+ lr.push_back(v); p1 = v;
+ } else {
+ 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.
+ lr.insert(lr.end(), rl.rbegin(), rl.rend()); // Tour, Knoten 0 doppelt.
}
diff --git a/graph/graph.tex b/graph/graph.tex
index 596c0d6..37356f6 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -1,34 +1,32 @@
\section{Graphen}
-\subsection{Minimale Spannbäume}
+% \subsection{Minimale Spannbäume}
-\paragraph{Schnitteigenschaft}
-Für jeden Schnitt $C$ im Graphen gilt:
-Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
-($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)
+% \paragraph{Schnitteigenschaft}
+% Für jeden Schnitt $C$ im Graphen gilt:
+% Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
+% ($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)
-\paragraph{Kreiseigenschaft}
-Für jeden Kreis $K$ im Graphen gilt:
-Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
-
-\subsubsection{Kruskal}
-\lstinputlisting{graph/kruskal.cpp}
+% \paragraph{Kreiseigenschaft}
+% Für jeden Kreis $K$ im Graphen gilt:
+% Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
\subsection{Kürzeste Wege}
-\subsubsection{Algorithmus von \textsc{Dijkstra}}
-Kürzeste Pfade in Graphen ohne negative Kanten.
+% \subsubsection{Algorithmus von \textsc{Dijkstra}}
+% Kürzeste Pfade in Graphen ohne negative Kanten.
\lstinputlisting{graph/dijkstra.cpp}
-\subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
-Kürzestes Pfade in Graphen mit negativen Kanten.
-Erkennt negative Zyklen.
+% \subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
+% Kürzestes Pfade in Graphen mit negativen Kanten.
+% Erkennt negative Zyklen.
\lstinputlisting{graph/bellmannFord.cpp}
-\subsubsection{\textsc{Floyd-Warshall}-Algorithmus}
-\lstinputlisting{graph/floydWarshall.cpp}
+% \subsubsection{\textsc{Floyd-Warshall}-Algorithmus}
+% \lstinputlisting{graph/floydWarshall.cpp}
+Floyd Warshall:
\begin{itemize}[nosep]
- \item Nur negative Werte sollten die Nullen überschreiben.
+ \item Nur negative Werte sollten die Nullen bei Schlingen überschreiben.
\item Von parallelen Kanten sollte nur die günstigste gespeichert werden.
\item \lstinline{i} liegt genau dann auf einem negativen Kreis, wenn \lstinline{dist[i][i] < 0} ist.
\item Wenn für \lstinline{c} gilt, dass \lstinline{dist[u][c] != INF && dist[c][v] != INF && dist[c][c] < 0}, wird der u-v-Pfad beliebig kurz.
@@ -60,7 +58,7 @@ VISIT(v):
\lstinputlisting{graph/euler.cpp}
\subsection{Lowest Common Ancestor}
-\lstinputlisting{graph/LCA.cpp}
+\lstinputlisting{graph/lca.cpp}
\subsection{Max-Flow}
@@ -68,9 +66,9 @@ VISIT(v):
Gut bei dünn besetzten Graphen.
\lstinputlisting{graph/capacityScaling.cpp}
-\subsubsection{Push Relabel}
-Gut bei sehr dicht besetzten Graphen.
-\lstinputlisting{graph/pushRelabel.cpp}
+% \subsubsection{Push Relabel}
+% Gut bei sehr dicht besetzten Graphen.
+% \lstinputlisting{graph/pushRelabel.cpp}
\subsubsection{Dinic's Algorithm mit Capacity Scaling}
Nochmal ca. Faktor 2 schneller als Ford Fulkerson mit Capacity Scaling.
@@ -103,6 +101,12 @@ Nochmal ca. Faktor 2 schneller als Ford Fulkerson mit Capacity Scaling.
\lstinputlisting{graph/maxCarBiMatch.cpp}
\lstinputlisting{graph/hopcroftKarp.cpp}
+\subsection{Maximum Weight Bipartite Matching}
+\lstinputlisting{graph/maxWeightBipartiteMatching.cpp}
+
+\subsection{Wert des maximalen Matchings}
+\lstinputlisting{graph/matching.cpp}
+
\subsection{2-SAT}
\lstinputlisting{graph/2sat.cpp}
diff --git a/graph/kruskal.cpp b/graph/kruskal.cpp
deleted file mode 100644
index 0bd2e22..0000000
--- a/graph/kruskal.cpp
+++ /dev/null
@@ -1,9 +0,0 @@
-// Union-Find Implementierung von oben. Laufzeit: O(|E|*log(|E|))
-sort(edges.begin(), edges.end());
-vector<ii> mst; int cost = 0;
-for (auto &e : edges) {
- if (findSet(e.from) != findSet(e.to)) {
- unionSets(e.from, e.to);
- mst.push_back(ii(e.from, e.to));
- cost += e.cost;
-}}
diff --git a/graph/lca.cpp b/graph/lca.cpp
new file mode 100644
index 0000000..d6548e9
--- /dev/null
+++ b/graph/lca.cpp
@@ -0,0 +1,28 @@
+struct LCA {
+ vector<int> depth, visited, first;
+ int idx;
+ SparseTable st;
+
+ void init(vector<vector<int>> &g, int root) { // Laufzeit: O(|V|)
+ depth.assign(2 * g.size(), 0);
+ visited.assign(2 * g.size(), -1);
+ first.assign(g.size(), 2 * g.size());
+ idx = 0;
+ visit(g, root, 0);
+ st.init(&depth);
+ }
+
+ void visit(vector<vector<int>> &g, int v, int d) {
+ visited[idx] = v, depth[idx] = d, first[v] = min(idx, first[v]), idx++;
+
+ for (int w : g[v]) {
+ if (first[w] == 2 * (int)g.size()) {
+ visit(g, w, d + 1);
+ visited[idx] = v, depth[idx] = d, idx++;
+ }}}
+
+ int getLCA(int a, int b) { // Laufzeit: O(1)
+ if (first[a] > first[b]) swap(a, b);
+ return visited[st.queryIdempotent(first[a], first[b])];
+ }
+};
diff --git a/graph/matching.cpp b/graph/matching.cpp
new file mode 100644
index 0000000..4383330
--- /dev/null
+++ b/graph/matching.cpp
@@ -0,0 +1,35 @@
+// Fehlerwahrscheinlichkeit: (n / MOD)^I
+const int N=200, MOD=1000000007, I=10;
+int n, adj[N][N], a[N][N];
+
+int rank() {
+ int r = 0;
+ for (int j = 0; j < n; j++) {
+ int k = r;
+ while (k < n && !a[k][j]) ++k;
+ if (k == n) continue;
+ swap(a[r], a[k]);
+ int inv = powmod(a[r][j], MOD - 2);
+ for (int i = j; i < n; i++)
+ a[r][i] = 1LL * a[r][i] * inv % MOD;
+ for (int u = r + 1; u < n; u++)
+ for (int v = j; v < n; v++)
+ a[u][v] = (a[u][v] - 1LL * a[r][v] * a[u][j] % MOD + MOD) % MOD;
+ ++r;
+ }
+ return r;
+}
+
+int max_matching() {
+ int ans = 0;
+ for (int _ = 0; _ < I; _++) {
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < i; j++) {
+ if (adj[i][j]) {
+ a[i][j] = rand() % (MOD - 1) + 1;
+ a[j][i] = MOD - a[i][j];
+ }}}
+ ans = max(ans, rank()/2);
+ }
+ return ans;
+}
diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp
index e538a19..24aebef 100644
--- a/graph/maxCarBiMatch.cpp
+++ b/graph/maxCarBiMatch.cpp
@@ -14,7 +14,7 @@ bool dfs(int v) {
}
int kuhn(int n) { // n = #Knoten links.
- pairs.assign(NUM_VERTICES, -1);
+ pairs.assign(adjlist.size(), -1);
int ans = 0;
// Greedy Matching. Optionale Beschleunigung.
for (int i = 0; i < n; i++) for (auto w : adjlist[i])
diff --git a/graph/maxWeightBipartiteMatching.cpp b/graph/maxWeightBipartiteMatching.cpp
new file mode 100644
index 0000000..f734fa4
--- /dev/null
+++ b/graph/maxWeightBipartiteMatching.cpp
@@ -0,0 +1,54 @@
+// Laufzeit: O(|V|^3)
+int costs[N_LEFT][N_RIGHT];
+
+// Es muss l<=r sein, ansonsten terminiert der Algorithmus nicht.
+int match(int l, int r) {
+ vector<int> xy(l, -1), yx(r, -1), lx(l), ly(r, 0), augmenting(r);
+ vector<bool> s(l);
+ vector<ii> slack(r, ii(0,0));
+
+ for (int x = 0; x < l; x++) lx[x] = *max_element(costs[x], costs[x] + r);
+ for (int root = 0; root < l; root++) {
+ fill(augmenting.begin(), augmenting.end(), -1);
+ fill(s.begin(), s.end(), false);
+ s[root] = true;
+ for (int y = 0; y < r; y++) {
+ slack[y] = ii(lx[root] + ly[y] - costs[root][y], root);
+ }
+ int y = -1;
+ for (;;) {
+ int delta = INT_MAX, x = -1;
+ for (int yy = 0; yy < r; yy++) {
+ if (augmenting[yy] == -1) {
+ if (slack[yy].first < delta) {
+ delta = slack[yy].first;
+ x = slack[yy].second;
+ y = yy;
+ }}}
+ if (delta > 0) {
+ for (int x = 0; x < l; x++) if (s[x]) lx[x] -= delta;
+ for (int y = 0; y < r; y++) {
+ if (augmenting[y] > -1) ly[y] += delta;
+ else slack[y].first -= delta;
+ }}
+ augmenting[y] = x;
+ x = yx[y];
+ if (x == -1) break;
+ s[x] = true;
+ for (int y = 0; y < r; y++) {
+ if (augmenting[y] == -1) {
+ ii alt = ii(lx[x] + ly[y] - costs[x][y], x);
+ if (slack[y].first > alt.first) {
+ slack[y] = alt;
+ }}}}
+ while (y != -1) {
+ // Jede Iteration vergrößert Matching um 1 (können 0-Kanten sein!).
+ int x = augmenting[y];
+ int prec = xy[x];
+ yx[y] = x;
+ xy[x] = y;
+ y = prec;
+ }}
+ return accumulate(lx.begin(), lx.end(), 0) +
+ accumulate(ly.begin(), ly.end(), 0); // Wert des Matchings.
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-24 23:47:20 +0000