Submit Info #37992

Problem Lang User Status Time Memory
Assignment Problem cpp (anonymous) AC 210 ms 2.62 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.37 MiB
hand_minus_00 AC 210 ms 2.55 MiB
hand_plus_00 AC 201 ms 2.55 MiB
max_random_00 AC 85 ms 2.62 MiB
max_random_01 AC 82 ms 2.55 MiB
max_random_02 AC 82 ms 2.55 MiB
max_random_03 AC 86 ms 2.55 MiB
max_random_04 AC 84 ms 2.55 MiB
random_00 AC 11 ms 0.92 MiB
random_01 AC 13 ms 0.92 MiB
random_02 AC 6 ms 0.67 MiB
random_03 AC 13 ms 0.91 MiB
random_04 AC 1 ms 0.60 MiB

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf = LLONG_MAX; struct minimum_cost_bipartite_matching { int nl, nr; ll mc = 0; vector<int> ml, mr, ly; minimum_cost_bipartite_matching(int nl, int nr, vector<vector<ll>> &c) : nl(nl), nr(nr), ml(nl, -1), mr(nr, -1), ly(nr) { vector<ll> s(nl), t(nr); for (int i = 0; i < nl; i++) { int x = i, y = -1; vector<bool> u(nr); vector<ll> md(nr, inf); while (x != -1) { ll ny = -1, d = inf; for (int j = 0; j < nr; j++) if (!u[j]) { ll v = c[x][j] - s[x] - t[j]; if (v < md[j]) md[j] = v, ly[j] = y; if (md[j] < d) d = md[j], ny = j; } s[i] += d; mc += d; for (int j = 0; j < nr; j++) if (u[j]) s[mr[j]] += d, t[j] -= d; else md[j] -= d; y = ny; u[y] = true; x = mr[y]; } while (y != -1) { mr[y] = ly[y] != -1 ? mr[ly[y]] : i; ml[mr[y]] = y; y = ly[y]; } } } }; int main() { int n; cin >> n; vector<vector<ll>> c(n, vector<ll>(n)); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> c[i][j]; minimum_cost_bipartite_matching mcbm(n, n, c); cout << mcbm.mc << "\n"; for (int i = 0; i < n; i++) cout << mcbm.ml[i] << (i < n - 1 ? " " : "\n"); }