Merevoli

Matching weight

Dec 4th, 2021
752
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct match_2 {
  2.     int n;
  3.     VI d, arg, trace, fx, fy, mx, my;
  4.     VVI cost, adj;
  5.     queue < int > qu;
  6.     void init(int _nx, int _ny) {
  7.         n = max(_nx, _ny);
  8.         cost = VVI(n, VI(n, oo));
  9.         adj = VVI(n);
  10.         d = VI(n);
  11.         arg = VI(n);
  12.         trace = VI(n);
  13.         fx = VI(n);
  14.         fy = VI(n);
  15.         mx = VI(n, -1);
  16.         my = VI(n, -1);
  17.     }
  18.     void add(int u, int v, int w) {
  19.         if (cost[u][v] == oo) adj[u].push_back(v);
  20.         if (cost[u][v] > w) cost[u][v] = w;
  21.     }
  22.     int getCost(int x, int y) {
  23.         return cost[x][y] - fx[x] - fy[y];
  24.     }
  25.     void initBFS(int start) {
  26.         for (int i = 0; i < n; i++) trace[i] = -1;
  27.         while (qu.size()) qu.pop();
  28.         qu.push(start);
  29.         for (int i = 0; i < n; i++) {
  30.             d[i] = getCost(start, i);
  31.             arg[i] = start;
  32.         }
  33.     }
  34.     int findPath() {
  35.         int x, y, w;
  36.         while (qu.size()) {
  37.             x = qu.front();
  38.             qu.pop();
  39.             for (int i = 0; i < adj[x].size(); i++) {
  40.                 y = adj[x][i];
  41.                 if (trace[y] == -1) {
  42.                     w = getCost(x, y);
  43.                     if (w == 0) {
  44.                         trace[y] = x;
  45.                         if (my[y] == -1) return y;
  46.                         qu.push(my[y]);
  47.                     }
  48.                     if (d[y] > w) {
  49.                         d[y] = w;
  50.                         arg[y] = x;
  51.                     }
  52.                 }
  53.             }
  54.         }
  55.         return -1;
  56.     }
  57.     int update(int start) {
  58.         int delta = oo;
  59.         for (int y = 0; y < n; y++)
  60.             if (trace[y] == -1) delta = min(delta, d[y]);
  61.         fx[start] += delta;
  62.         for (int y = 0, x; y < n; y++)
  63.             if (trace[y] != -1) {
  64.                 x = my[y];
  65.                 fx[x] += delta;
  66.                 fy[y] -= delta;
  67.             }
  68.         else d[y] -= delta;
  69.         for (int y = 0; y < n; y++)
  70.             if (trace[y] == -1 && d[y] == 0) {
  71.                 trace[y] = arg[y];
  72.                 if (my[y] == -1) return y;
  73.                 qu.push(my[y]);
  74.             }
  75.         return -1;
  76.     }
  77.     void enlarge(int finish) {
  78.         for (int y = finish, x, yy; y != -1;) {
  79.             x = trace[y];
  80.             yy = mx[x];
  81.             mx[x] = y;
  82.             my[y] = x;
  83.             y = yy;
  84.         }
  85.     }
  86.     int maxMatching() {
  87.         for (int x = 0; x < n; x++) {
  88.             initBFS(x);
  89.             int finish = -1;
  90.             while (finish == -1) {
  91.                 finish = findPath();
  92.                 if (finish != -1) break;
  93.                 finish = update(x);
  94.             }
  95.             enlarge(finish);
  96.         }
  97.         int total = 0;
  98.         for (int x = 0; x < n; x++)
  99.             if (cost[x][mx[x]] != oo) total += cost[x][mx[x]];
  100.         return total;
  101.     }
  102. }
  103. match2;
  104. void solve_match2() {
  105.     int n, u, v, w;
  106.     cin >> n;
  107.     match2.init(n + 1, n + 1);
  108.     while (cin >> u >> v >> w) {
  109.         match2.add(u, v, w);
  110.     }
  111.     cout << match2.maxMatching() << "\n";
  112.     for (int x = 1, y; x <= n; x++) {
  113.         y = match2.mx[x];
  114.         if (y != -1) cout << x << " " << y << "\n";
  115.     }
  116. }
RAW Paste Data