Merevoli

Matching un-weight

Dec 4th, 2021
719
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const int maxn = 1010,
  2.     maxm = 50010;
  3. struct match_0 {
  4.     int n, m, start, finish, newroot, qsize, adj[maxm], next[maxm], last[maxn],
  5.         mat[maxn], que[maxn], dad[maxn], root[maxn];
  6.     bool inque[maxn], inpath[maxn], inblossom[maxn];
  7.     void init(int _n) {
  8.         n = _n;
  9.         m = 0;
  10.         for (int x = 1; x <= n; x++) {
  11.             last[x] = -1;
  12.             mat[x] = 0;
  13.         }
  14.     }
  15.     void add(int u, int v) {
  16.         adj[m] = v;
  17.         next[m] = last[u];
  18.         last[u] = m++;
  19.     }
  20.     int lca(int u, int v) {
  21.         for (int x = 1; x <= n; x++) inpath[x] = 0;
  22.         while (true) {
  23.             u = root[u];
  24.             inpath[u] = 1;
  25.             if (u == start) break;
  26.             u = dad[mat[u]];
  27.         }
  28.         while (true) {
  29.             v = root[v];
  30.             if (inpath[v]) break;
  31.             v = dad[mat[v]];
  32.         }
  33.         return v;
  34.     }
  35.     void trace(int u) {
  36.         while (root[u] != newroot) {
  37.             int v = mat[u];
  38.             inblossom[root[u]] = 1;
  39.             inblossom[root[v]] = 1;
  40.             u = dad[v];
  41.             if (root[u] != newroot) dad[u] = v;
  42.         }
  43.     }
  44.     void blossom(int u, int v) {
  45.         for (int x = 1; x <= n; x++) inblossom[x] = 0;
  46.         newroot = lca(u, v);
  47.         trace(u);
  48.         trace(v);
  49.         if (root[u] != newroot) dad[u] = v;
  50.         if (root[v] != newroot) dad[v] = u;
  51.         for (int x = 1; x <= n; x++) {
  52.             if (inblossom[root[x]]) {
  53.                 root[x] = newroot;
  54.                 if (!inque[x]) {
  55.                     inque[x] = 1;
  56.                     que[qsize++] = x;
  57.                 }
  58.             }
  59.         }
  60.     }
  61.     bool bfs() {
  62.         for (int x = 1; x <= n; x++) {
  63.             inque[x] = 0;
  64.             dad[x] = 0;
  65.             root[x] = x;
  66.         }
  67.         qsize = 0;
  68.         que[qsize++] = start;
  69.         inque[start] = 1;
  70.         finish = 0;
  71.         for (int i = 0, u; i < qsize; i++) {
  72.             u = que[i];
  73.             for (int e = last[u], v; e != -1; e = next[e]) {
  74.                 v = adj[e];
  75.                 if (root[v] != root[u] && v != mat[u]) {
  76.                     if (v == start || (mat[v] > 0 && dad[mat[v]] > 0)) blossom(u, v);
  77.                     else if (dad[v] == 0) {
  78.                         dad[v] = u;
  79.                         if (mat[v] > 0) que[qsize++] = mat[v];
  80.                         else {
  81.                             finish = v;
  82.                             return true;
  83.                         }
  84.                     }
  85.                 }
  86.             }
  87.         }
  88.         return false;
  89.     }
  90.     void enlarge() {
  91.         int u = finish, v, x;
  92.         while (u > 0) {
  93.             v = dad[u];
  94.             x = mat[v];
  95.             mat[v] = u;
  96.             mat[u] = v;
  97.             u = x;
  98.         }
  99.     }
  100.     int maxMatching() {
  101.         for (int x = 1; x <= n; x++)
  102.             if (mat[x] == 0) {
  103.                 start = x;
  104.                 if (bfs()) enlarge();
  105.             }
  106.         int total = 0;
  107.         for (int x = 1; x <= n; x++)
  108.             if (mat[x] > x) total++;
  109.         return total;
  110.     }
  111. }
  112. match0;
  113. void solve_match0() {
  114.     int n, m, u, v, k;
  115.     cin >> n >> m;
  116.     match0.init(n + m);
  117.     while (cin >> u >> v) {
  118.         v += n;
  119.         match0.add(u, v);
  120.         match0.add(v, u);
  121.     }
  122.     cout << match0.maxMatching() << "\n";
  123.     for (int x = 1, y; x <= n; x++) {
  124.         y = match0.mat[x];
  125.         if (y != 0) cout << x << " " << y - n << "\n";
  126.     }
  127. }
RAW Paste Data