Submit Info #41224

Problem Lang User Status Time Memory
Assignment Problem cpp-acl (anonymous) AC 108 ms 2.66 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
hand_minus_00 AC 89 ms 2.66 MiB
hand_plus_00 AC 108 ms 2.55 MiB
max_random_00 AC 33 ms 2.61 MiB
max_random_01 AC 32 ms 2.61 MiB
max_random_02 AC 33 ms 2.61 MiB
max_random_03 AC 34 ms 2.55 MiB
max_random_04 AC 32 ms 2.60 MiB
random_00 AC 5 ms 1.30 MiB
random_01 AC 8 ms 1.36 MiB
random_02 AC 2 ms 1.05 MiB
random_03 AC 8 ms 1.44 MiB
random_04 AC 1 ms 0.69 MiB

#include <bits/stdc++.h> using namespace std; using ll = int64_t; const ll INF = 1e18; const int maxn = 501; struct KM { ll w[maxn][maxn]; ll lx[maxn], ly[maxn]; ll slack[maxn]; bool visx[maxn], visy[maxn]; int n; int match[maxn]; bool dfs(int i, bool aug) { if (visx[i]) return false; visx[i] = true; for (int j = 0; j < n; j++) { ll d = lx[i] + ly[j] - w[i][j]; if (d == 0) { visy[j] = true; if (match[j] == -1 || dfs(match[j], aug)) { if (aug) match[j] = i; return true; } } else { slack[j] = min(slack[j], d); } } return false; } bool augment() { for (int i = 0; i < n; i++) { if (slack[i] == 0) { visy[i] = true; if (match[i] == -1 || dfs(match[i], false)) { return true; } } } return false; } void relabel() { ll d = INF; for (int i = 0; i < n; i++) if (!visy[i]) d = min(d, slack[i]); // cerr << d << '\n'; for (int i = 0; i < n; i++) if (visx[i]) lx[i] -= d; for (int i = 0; i < n; i++) { if (visy[i]) ly[i] += d; else slack[i] -= d; } } ll solve() { for (int i = 0; i < n; i++) { lx[i] = INF; ly[i] = 0; match[i] = -1; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) slack[j] = INF; for (int j = 0; j < n; j++) visx[j] = visy[j] = false; if (dfs(i, true)) continue; while (!augment()) relabel(); for (int j = 0; j < n; j++) visx[j] = visy[j] = false; assert( dfs(i, true) ); } ll ans = 0; for (int i = 0; i < n; i++) { assert( match[i] != -1 ); ans += w[match[i]][i]; } return ans; } } km; signed main() { ios_base::sync_with_stdio(0), cin.tie(0); const ll M = 1e9; int n; while (cin >> n && n) { km.n = n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int c; cin >> c; km.w[j][i] = max<ll>(0, M-c); } } cout << M * n - km.solve() << '\n'; for (int i = 0; i < n; i++) cout << km.match[i] << ' '; cout << '\n'; } }