Submit Info #987

Problem Lang User Status Time Memory
Matching on General Graph cpp14 hos AC 16 ms 1.53 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.53 MiB
example_01 AC 6 ms 0.51 MiB
max_random_00 AC 11 ms 1.50 MiB
max_random_01 AC 16 ms 1.51 MiB
random_00 AC 5 ms 0.80 MiB
random_01 AC 8 ms 0.88 MiB
sparse_00 AC 14 ms 1.43 MiB
sparse_01 AC 9 ms 1.46 MiB
sparse_02 AC 9 ms 1.50 MiB
sparse_03 AC 13 ms 1.53 MiB
sparse_04 AC 11 ms 1.43 MiB

#include <stdio.h> #include <algorithm> template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } unsigned xrand() { static unsigned x = 314159265, y = 358979323, z = 846264338, w = 327950288; unsigned t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8; } template<class T> struct UsoMatching { static constexpr int MAX_N = 510; static constexpr int NUM_ITERS = 2; int n; T adj[MAX_N][MAX_N]; int mate[MAX_N]; UsoMatching(int n_) : n(n_) { if (n & 1) ++n; for (int u = 0; u < n; ++u) std::fill(adj[u], adj[u] + n, 0); } void addEdge(int u, int v, T c) { chmax(adj[u][v], c); chmax(adj[v][u], c); } int perm[MAX_N]; int usLen; int us[MAX_N]; bool on[MAX_N]; T ds[MAX_N]; bool dfs(int u) { us[usLen++] = u; if (on[u]) return true; on[u] = true; for (int j = 0; j < n; ++j) { const int v = perm[j]; if (v != u && v != mate[u] && !on[v]) { const int w = mate[v]; const T d = ds[u] + adj[u][v] - adj[v][w]; if (ds[w] < d) { ds[w] = d; if (dfs(w)) return true; } } } --usLen; on[u] = false; return false; } T run() { for (int u = 0; u < n; ++u) mate[u] = u ^ 1, perm[u] = u; for (int iter = 0; iter < NUM_ITERS; ++iter) { loop: for (int u = 1; u < n; ++u) std::swap(perm[xrand() % (u + 1)], perm[u]); usLen = 0; std::fill(on, on + n, false); std::fill(ds, ds + n, 0); for (int j = 0; j < n; ++j) { if (dfs(perm[j])) { for (int k = usLen - 1; k--; ) if (us[k] == us[usLen - 1]) { const int t = mate[us[k]]; for (int l = k; l < usLen - 2; ++l) mate[us[l]] = mate[us[l + 1]]; mate[us[usLen - 2]] = t; for (int l = k; l < usLen - 1; ++l) mate[mate[us[l]]] = us[l]; goto loop; } } } } T ret = 0; for (int u = 0; u < n; ++u) if (u < mate[u]) ret += adj[u][mate[u]]; return ret; } }; int main() { int N, M; scanf("%d%d", &N, &M); UsoMatching<int> um(N); for (int i = 0; i < M; ++i) { int u, v; scanf("%d%d", &u, &v); um.addEdge(u, v, 1); } const int res = um.run(); printf("%d\n", res); for (int u = 0; u < N; ++u) { if (u < um.mate[u] && um.adj[u][um.mate[u]] > 0) { printf("%d %d\n", u, um.mate[u]); } } return 0; }