Submit Info #67381

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
hand_minus_00 AC 174 ms 2.32 MiB
hand_plus_00 AC 170 ms 2.37 MiB
max_random_00 AC 41 ms 2.37 MiB
max_random_01 AC 38 ms 2.32 MiB
max_random_02 AC 38 ms 2.37 MiB
max_random_03 AC 42 ms 2.40 MiB
max_random_04 AC 40 ms 2.32 MiB
random_00 AC 5 ms 0.61 MiB
random_01 AC 6 ms 0.70 MiB
random_02 AC 2 ms 0.45 MiB
random_03 AC 6 ms 0.70 MiB
random_04 AC 1 ms 0.45 MiB

#include <bits/stdc++.h> using namespace std; using ll = long long; #define sz(x) int((x).size()) #define rep(i, l, r) for (int i = (l); i < (r); i++) const ll INF = 1ll << 60; using T = ll; pair<T, vector<int>> hungarian(const vector<vector<T>> &a) { if (a.empty()) return {0, {}}; int n = sz(a) + 1, m = sz(a[0]) + 1; vector<T> u(n), v(m); vector<int> p(m), ans(n - 1); rep(i,1,n) { p[0] = i; int j0 = 0; // add "dummy" worker 0 vector<T> dist(m, INF); vector<int> pre(m, -1); vector<bool> done(m + 1); do { // dijkstra done[j0] = true; int i0 = p[j0], j1; T delta = INF; rep(j,1,m) if (!done[j]) { T cur = a[i0 - 1][j - 1] - u[i0] - v[j]; if (cur < dist[j]) dist[j] = cur, pre[j] = j0; if (dist[j] < delta) delta = dist[j], j1 = j; } rep(j,0,m) { if (done[j]) u[p[j]] += delta, v[j] -= delta; else dist[j] -= delta; } j0 = j1; } while (p[j0]); while (j0) { // update alternating path int j1 = pre[j0]; p[j0] = p[j1], j0 = j1; } } rep(j,1,m) if (p[j]) ans[p[j] - 1] = j - 1; return {-v[0], ans}; // min cost } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<vector<ll>> cost(n, vector<ll>(n)); for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { cin >> cost[u][v]; } } auto [ans, match] = hungarian(cost); cout << ans << "\n"; for (int u = 0; u < n; u++) { cout << match[u] << " \n"[u == n - 1]; } }