Submit Info #67368

Problem Lang User Status Time Memory
Assignment Problem cpp Emilan AC 192 ms 2.40 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
hand_minus_00 AC 185 ms 2.32 MiB
hand_plus_00 AC 192 ms 2.37 MiB
max_random_00 AC 46 ms 2.38 MiB
max_random_01 AC 42 ms 2.40 MiB
max_random_02 AC 41 ms 2.28 MiB
max_random_03 AC 49 ms 2.32 MiB
max_random_04 AC 46 ms 2.32 MiB
random_00 AC 5 ms 0.70 MiB
random_01 AC 6 ms 0.78 MiB
random_02 AC 2 ms 0.45 MiB
random_03 AC 7 ms 0.75 MiB
random_04 AC 1 ms 0.45 MiB

#include <bits/stdc++.h> using namespace std; using ll = long long; // https://github.com/yosupo06/library-checker-problems/blob/master/graph/assignment/sol/correct.cpp struct Hungarian { template <class T> using V = vector<T>; using D = long long; V<D> le, ri; V<int> perm; Hungarian(const vector<V<D>> &c) { int n = int(c.size()), m = int(c[0].size()); assert(n <= m); le = V<D>(n, D(0)); ri = V<D>(m, D(0)); perm = V<int>(n); V<int> to_r(n, -1), to_l(m, -1); for (int s = 0; s < n; s++) { V<char> l_u(n), r_u(m); l_u[s] = true; V<int> tr(m, -1), min_l(m, s); V<D> min_cost(m); for (int j = 0; j < m; j++) min_cost[j] = c[s][j] + le[s] + ri[j]; while (true) { int r = -1; D d = numeric_limits<D>::max(); for (int j = 0; j < m; j++) { if (!r_u[j] && min_cost[j] < d) { r = j; d = min_cost[j]; } } for (int i = 0; i < n; i++) if (l_u[i]) le[i] -= d; for (int j = 0; j < m; j++) { if (r_u[j]) ri[j] += d; else min_cost[j] -= d; } tr[r] = min_l[r]; int l = to_l[r]; if (l == -1) { while (r != -1) { int nl = tr[r], nr = to_r[nl]; to_l[r] = nl; to_r[nl] = r; r = nr; } break; } l_u[l] = r_u[r] = true; for (int j = 0; j < m; j++) { D cost = c[l][j] + le[l] + ri[j]; if (cost < min_cost[j]) { min_l[j] = l; min_cost[j] = cost; } } } } perm = to_r; } }; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<vector<ll>> adj(n, vector<ll>(n)); for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { cin >> adj[u][v]; } } Hungarian km(adj); ll ans = 0; for (int u = 0; u < n; u++) { ans += adj[u][ km.perm[u] ]; } cout << ans << "\n"; for (int u = 0; u < n; u++) { cout << km.perm[u] << " \n"[u == n - 1]; } }