From fe5fa1141efeb7454c763dbd2645fb4ff04487a3 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 28 Mar 2023 13:25:59 +0200 Subject: merged --- graph/matching.cpp | 32 +++++++------------------------- 1 file changed, 7 insertions(+), 25 deletions(-) (limited to 'graph/matching.cpp') diff --git a/graph/matching.cpp b/graph/matching.cpp index ddd1c81..2deb672 100644 --- a/graph/matching.cpp +++ b/graph/matching.cpp @@ -1,32 +1,9 @@ constexpr int MOD=1'000'000'007, I=10; vector> adjlist, mat; -int gauss(int n, ll p) { - int rank = n; - for (int line = 0; line < n; line++) { - int swappee = line; - while (swappee < n && mat[swappee][line] == 0) swappee++; - if (swappee == n) {rank--; continue;} - swap(mat[line], mat[swappee]); - ll factor = powMod(mat[line][line], p - 2, p); - for (int i = 0; i < n; i++) { - mat[line][i] *= factor; - mat[line][i] %= p; - } - for (int i = 0; i < n; i++) { - if (i == line) continue; - ll diff = mat[i][line]; - for (int j = 0; j < n; j++) { - mat[i][j] -= (diff * mat[line][j]) % p; - mat[i][j] %= p; - if (mat[i][j] < 0) mat[i][j] += p; - }}} - return rank; -} - int max_matching() { int ans = 0; - mat.assign(sz(adjlist), vector(sz(adjlist))); + mat.assign(sz(adjlist), {}); for (int _ = 0; _ < I; _++) { for (int i = 0; i < sz(adjlist); i++) { mat[i].assign(sz(adjlist), 0); @@ -35,7 +12,12 @@ int max_matching() { mat[i][j] = rand() % (MOD - 1) + 1; mat[j][i] = MOD - mat[i][j]; }}} - ans = max(ans, gauss(sz(adjlist), MOD)/2); + gauss(sz(adjlist), MOD); //LGS unten + int rank = 0; + for (auto& row : mat) { + if (*min_element(all(row)) != 0) rank++; + } + ans = max(ans, rank / 2); } return ans; } -- cgit v1.2.3