Submit Info #52741

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.71 MiB
hand_minus_00 AC 71 ms 1.72 MiB
hand_plus_00 AC 81 ms 1.70 MiB
max_random_00 AC 37 ms 1.71 MiB
max_random_01 AC 37 ms 1.71 MiB
max_random_02 AC 37 ms 1.71 MiB
max_random_03 AC 39 ms 1.71 MiB
max_random_04 AC 38 ms 1.72 MiB
random_00 AC 5 ms 1.08 MiB
random_01 AC 6 ms 1.09 MiB
random_02 AC 2 ms 0.84 MiB
random_03 AC 6 ms 1.09 MiB
random_04 AC 1 ms 0.71 MiB

#include <bits/stdc++.h> using namespace std; #define TIME Timer __timer(__PRETTY_FUNCTION__) class Timer { private: std::string title; chrono::high_resolution_clock::time_point start; public: Timer(std::string t) : title(t), start(chrono::high_resolution_clock::now()) {} ~Timer() { auto finish = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::microseconds>(finish - start).count(); double ms = double(duration) * 0.001; std::cerr << "Timer: " << title << " takes " << ms << " ms to finish.\n"; } }; using ll = long long; const int maxn = 525, inf = 1e9; const int M = 1e9; const ll INF = 1e9; struct KuhnMunkres { int n; int w[maxn][maxn]; int match[maxn]; ll lx[maxn], ly[maxn], slack[maxn]; bool visx[maxn], visy[maxn]; void addEdge(int a, int b, int c) { w[a][b] = c; } bool dfs(int i, bool aug) { if (visx[i]) return false; visx[i] = true; for (int j = 0; j < n; j++) if (!visy[j]) { ll d = lx[i] + ly[j] - w[i][j]; if (d) { slack[j] = min(slack[j], d); } else { visy[j] = true; if (match[j] == -1 || dfs(match[j], aug)) { if (aug) match[j] = i; return true; } } } return false; } bool augment() { for (int i = 0; i < n; i++) if (!visy[i] && 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]); // assert( d != inf ); 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; for (int i = 0; i < n; i++) if (!visy[i]) slack[i] -= d; } void solve() { for (int i = 0; i < n; i++) { match[i] = -1; lx[i] = INF; ly[i] = 0; } for (int i = 0; i < n; i++) { // debug(i); fill(visx, visx+n, false); fill(visy, visy+n, false); fill(slack, slack+n, INF); if (dfs(i, true)) continue; while (!augment()) relabel(); fill(visx, visx+n, false); fill(visy, visy+n, false); dfs(i, true); } long long ans = 0; for (int i = 0; i < n; i++) ans += w[match[i]][i]; ans = 1LL * M * n - ans; cout << ans << '\n'; for (int i = 0; i < n; i++) cout << match[i] << (i+1==n ? '\n' : ' '); } } KM; signed main() { TIME; ios_base::sync_with_stdio(0), cin.tie(0); int n; cin >> n; KM.n = n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int c; cin >> c; KM.addEdge(j, i, M - c); } } KM.solve(); }