Submit Info #53522

Problem Lang User Status Time Memory
Assignment Problem cpp WeakestTopology AC 163 ms 2.60 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
hand_minus_00 AC 163 ms 2.59 MiB
hand_plus_00 AC 160 ms 2.58 MiB
max_random_00 AC 43 ms 2.58 MiB
max_random_01 AC 38 ms 2.60 MiB
max_random_02 AC 38 ms 2.60 MiB
max_random_03 AC 43 ms 2.59 MiB
max_random_04 AC 41 ms 2.59 MiB
random_00 AC 5 ms 0.95 MiB
random_01 AC 6 ms 0.96 MiB
random_02 AC 2 ms 0.71 MiB
random_03 AC 6 ms 0.96 MiB
random_04 AC 1 ms 0.71 MiB

#include <bits/stdc++.h> using namespace std; using ll = long long; template<typename T> struct Hungarian { inline static const T inf = numeric_limits<T>::max(); int N, M; T cost; vector<int> match; vector<T> ldual, rdual; vector<vector<T>> C; Hungarian(int N, int M) : N(N), M(M), cost(0), match(M, -1), ldual(N), rdual(M), C(N) {} void insert(int u, const vector<T>& row) { C[u] = row; ldual[u] = inf; for (int v = 0; v < M; ++v) { ldual[u] = min(ldual[u], C[u][v] - rdual[v]); } vector<T> dmin(M, inf); vector<int> best(M, -1); vector<bool> vis(M); int last = -1; for (int z = u; z != -1; z = match[last]) { T delta = inf; int next = -1; for (int v = 0; v < M; ++v) { if (vis[v]) continue; T d = C[z][v] - ldual[z] - rdual[v]; if (d < dmin[v]) { dmin[v] = d; best[v] = last; } if (dmin[v] < delta) { delta = dmin[v]; next = v; } } for (int v = 0; v < M; ++v) { if (vis[v]) { ldual[match[v]] += delta; rdual[v] -= delta; } else { dmin[v] -= delta; } } ldual[u] += delta; last = next; vis[last] = true; } for (int v = last; v != -1; v = best[v]) { if (best[v] == -1) { match[v] = u; } else { int z = match[best[v]]; cost -= C[z][best[v]]; match[v] = z; } cost += C[match[v]][v]; } } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; Hungarian<ll> h(N, N); for (int u = 0; u < N; ++u) { vector<ll> row(N); for (int v = 0; v < N; ++v) { cin >> row[v]; } h.insert(u, row); } vector<int> inv(N); for (int v = 0; v < N; ++v) { inv[h.match[v]] = v; } cout << h.cost << '\n'; for (int u = 0; u < N; ++u) { cout << inv[u] << "\n "[u + 1 < N]; } exit(0); }