Submit Info #45929

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
hand_minus_00 AC 128 ms 2.58 MiB
hand_plus_00 AC 127 ms 2.60 MiB
max_random_00 AC 36 ms 2.61 MiB
max_random_01 AC 37 ms 2.62 MiB
max_random_02 AC 36 ms 2.55 MiB
max_random_03 AC 37 ms 2.55 MiB
max_random_04 AC 37 ms 2.59 MiB
random_00 AC 6 ms 0.93 MiB
random_01 AC 6 ms 0.96 MiB
random_02 AC 5 ms 0.75 MiB
random_03 AC 8 ms 0.93 MiB
random_04 AC 1 ms 0.61 MiB

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const ll INF = 1LL << 60; struct Hungarian { int n; vector<int> matchS, matchT, slackx; vector<bool> S, T; vector<vector<ll>> C; vector<ll> slack, LS, LT; Hungarian(int _n) : n(_n), matchS(n, -1), matchT(n, -1), slackx(n, -1), S(n), T(n), C(n, vector<ll>(n)), slack(n), LS(n), LT(n) {} ll solve() { for (int i = 0; i < n; ++i) { LS[i] = *max_element(C[i].begin(), C[i].end()); } for (int matches = 0; matches < n; ++matches) { int root; fill(slack.begin(), slack.end(), 0); fill(S.begin(), S.end(), false); fill(T.begin(), T.end(), false); for (int i = 0; i < n; ++i) if (matchS[i] == -1) root = i; S[root] = true; for (int j = 0; j < n; ++j) { slack[j] = LS[root] + LT[j] - C[root][j]; slackx[j] = root; } for (;;) { // Find something with zero slack but not in T int y = -1; for (int i = 0; i < n; ++i) if (!slack[i] && !T[i]) y = i; if (y == -1) { ll delta = INF; for (int i = 0; i < n; ++i) if (slack[i]) delta = min(delta, slack[i]); for (int i = 0; i < n; ++i) { if (T[i]) LT[i] += delta; if (S[i]) LS[i] -= delta; if (slack[i]) slack[i] -= delta; if (!slack[i] && !T[i]) y = i; } } if (matchT[y] == -1) { // Augment path from y..root for (int z = y;;) { int x = matchS[slackx[z]]; matchT[z] = slackx[z]; matchS[slackx[z]] = z; if (slackx[z] == root) break; z = x; } break; } int z = matchT[y]; S[z] = T[y] = true; for (int i = 0; i < n; ++i) { ll v = LS[z] + LT[i] - C[z][i]; if (v < slack[i]) { slack[i] = v; slackx[i] = z; } } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { assert(LS[i] + LT[j] >= C[i][j]); } assert(LS[i] + LT[matchS[i]] == C[i][matchS[i]]); } ll ans = 0; for (int i = 0; i < n; ++i) ans += C[i][matchS[i]]; return ans; } }; int main() { int n; scanf("%d", &n); Hungarian g(n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { ll c; scanf("%lld", &c); g.C[i][j] = -c; } ll ans = -g.solve(); printf("%lld\n", ans); for (int i = 0; i < n; ++i) printf("%d ", g.matchS[i]); }