Submit Info #41727

Problem Lang User Status Time Memory
Assignment Problem cpp wleungBVG AC 228 ms 4.55 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
hand_minus_00 AC 228 ms 4.49 MiB
hand_plus_00 AC 219 ms 4.55 MiB
max_random_00 AC 47 ms 4.55 MiB
max_random_01 AC 42 ms 4.55 MiB
max_random_02 AC 42 ms 4.54 MiB
max_random_03 AC 48 ms 4.55 MiB
max_random_04 AC 44 ms 4.55 MiB
random_00 AC 6 ms 1.17 MiB
random_01 AC 5 ms 1.24 MiB
random_02 AC 2 ms 0.75 MiB
random_03 AC 9 ms 1.27 MiB
random_04 AC 1 ms 0.67 MiB

// https://judge.yosupo.jp/problem/assignment #include <bits/stdc++.h> using namespace std; template<class C>constexpr int sz(const C&c){return int(c.size());} using ll=long long;constexpr const char nl='\n',sp=' '; template <class T> struct HungarianAlgorithm { int N, M; T cost; vector<int> jobForWorker, workerForJob; HungarianAlgorithm(vector<vector<T>> A, T INF = numeric_limits<T>::max()) : N(A.size()), M(A.empty() ? 0 : A[0].size()), cost(T()) { bool rev = N > M; if (rev) { swap(N, M); vector<vector<T>> B(N, vector<T>(M)); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) B[i][j] = A[j][i]; A.swap(B); } jobForWorker.assign(N, -1); workerForJob.assign(M + 1, N); auto add = [&] (pair<int, T> &a, const pair<int, T> &b) { a.first += b.first; a.second += b.second; }; auto sub = [&] (pair<int, T> &a, const pair<int, T> &b) { a.first -= b.first; a.second -= b.second; }; vector<pair<int, T>> d1(N + 1, make_pair(0, T())); vector<pair<int, T>> d2(M + 1, make_pair(0, T())); for (int i = 0; i < N; i++) { int j0 = M; workerForJob[j0] = i; vector<pair<int, T>> dist(M + 1, make_pair(1, T())); vector<int> par(M + 1, -1); vector<bool> done(M + 1, false); do { done[j0] = true; int i0 = workerForJob[j0], j1 = M; pair<int, T> delta = make_pair(1, T()); for (int j = 0; j < M; j++) if (!done[j]) { pair<int, T> d = A[i0][j] == INF ? make_pair(1, T()) : make_pair(0, A[i0][j]); sub(d, d1[i0]); sub(d, d2[j]); if (d < dist[j]) { dist[j] = d; par[j] = j0; } if (dist[j] < delta) delta = dist[j1 = j]; } j0 = j1; for (int j = 0; j <= M; j++) { if (done[j]) { add(d1[workerForJob[j]], delta); sub(d2[j], delta); } else sub(dist[j], delta); } } while (workerForJob[j0] != N); for (; j0 != M; j0 = par[j0]) workerForJob[j0] = workerForJob[par[j0]]; } workerForJob.pop_back(); for (int j = 0; j < M; j++) { if (workerForJob[j] == N) workerForJob[j] = -1; else jobForWorker[workerForJob[j]] = j; } cost = d2[M].first < 0 ? INF : d2[M].first > 0 ? -INF : -d2[M].second; if (rev) { swap(N, M); jobForWorker.swap(workerForJob); } } }; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // freopen("err.txt", "w", stderr); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin >> N; vector<vector<ll>> A(N, vector<ll>(N)); for (auto &&ai : A) for (auto &&aij : ai) cin >> aij; HungarianAlgorithm<ll> HA(A); cout << HA.cost << nl; for (int i = 0; i < N; i++) cout << HA.jobForWorker[i] << " \n"[i == N - 1]; return 0; }