diff options
Diffstat (limited to 'content')
| -rw-r--r-- | content/graph/matching.cpp | 17 | ||||
| -rw-r--r-- | content/math/lgsFp.cpp | 13 |
2 files changed, 14 insertions, 16 deletions
diff --git a/content/graph/matching.cpp b/content/graph/matching.cpp index 3619d7c..f0f34a3 100644 --- a/content/graph/matching.cpp +++ b/content/graph/matching.cpp @@ -1,22 +1,17 @@ -constexpr int MOD=1'000'000'007, I=10; -vector<vector<ll>> adj, mat; +constexpr int mod = 1'000'000'007, I = 10; -int max_matching() { +int max_matching(const vector<vector<int>> &adj) { int ans = 0; - mat.assign(ssize(adj), {}); + vector<vector<ll>> mat(ssize(adj)); for (int _ = 0; _ < I; _++) { for (int v = 0; v < ssize(adj); v++) { mat[v].assign(ssize(adj), 0); for (int u : adj[v]) { if (u < v) { - mat[v][u] = rand() % (MOD - 1) + 1; - mat[u][v] = MOD - mat[v][u]; + mat[v][u] = rand() % (mod - 1) + 1; + mat[u][v] = mod - mat[v][u]; }}} - gauss(ssize(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ - int rank = 0; - for (auto& row : mat) { - if (*ranges::max_element(row) != 0) rank++; - } + int rank = ssize(gauss(mat)); // LGS @\sourceref{math/lgsFp.cpp}@ ans = max(ans, rank / 2); } return ans; diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp index 4c12477..5028782 100644 --- a/content/math/lgsFp.cpp +++ b/content/math/lgsFp.cpp @@ -1,6 +1,7 @@ -vector<int> pivots; // ith pivot is in ith row -void gauss(int n, int m) { - for (int r = 0, c = 0; c < m; c++) { +vector<int> gauss(vector<vector<ll>> &mat) { + int n = ssize(mat), m = ssize(mat[0]); + vector<int> pivots; // ith pivot is in ith row + for (int r = 0, c = 0; r < n && c < m; c++) { for (int i = r; i < n; i++) { if (mat[i][c] != 0){ swap(mat[r], mat[i]); @@ -16,5 +17,7 @@ void gauss(int n, int m) { mat[i][j] = (mat[i][j] - f*mat[r][j] % mod + mod) % mod; }} pivots.push_back(c); - if (++r == n) break; -}} // no solution if pivots.back() == m-1 + r++; + } + return pivots; // no solution if pivots.back() == m-1 +} |