Adding code for the value of the maximum matching.

2 files changed, 38 insertions, 0 deletions

diff --git a/graph/graph.tex b/graph/graph.tex
index 3aa5b31..711bdcf 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -100,6 +100,9 @@ Nochmal ca. Faktor 2 schneller als Ford Fulkerson mit Capacity Scaling.
 \lstinputlisting{graph/maxCarBiMatch.cpp}
 \lstinputlisting{graph/hopcroftKarp.cpp}
 
+\subsection{Wert des maximalen Matchings}
+\lstinputlisting{graph/matching.cpp}
+
 \subsection{2-SAT}
 \lstinputlisting{graph/2sat.cpp}
 
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;
+}