Submit Info #53836

Problem Lang User Status Time Memory
Assignment Problem cpp mickeyandkaka AC 93 ms 3.72 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.71 MiB
hand_minus_00 AC 93 ms 3.58 MiB
hand_plus_00 AC 90 ms 3.71 MiB
max_random_00 AC 36 ms 3.71 MiB
max_random_01 AC 35 ms 3.72 MiB
max_random_02 AC 35 ms 3.71 MiB
max_random_03 AC 38 ms 3.70 MiB
max_random_04 AC 35 ms 3.71 MiB
random_00 AC 5 ms 1.33 MiB
random_01 AC 6 ms 1.34 MiB
random_02 AC 2 ms 0.96 MiB
random_03 AC 6 ms 1.34 MiB
random_04 AC 1 ms 0.71 MiB

//{{{ #include <bits/stdc++.h> using namespace std; using LL = long long; using VLL = vector<LL>; using vi = vector<int>; using pii = pair<int, int>; #define sz(x) (int)((x).size()) #define all(x) (x).begin(), (x).end() #define clr(a, b) memset(a, b, sizeof(a)) #ifdef LOCAL #include "prettyprint.hpp" // clang-format off void _print() { cerr << "]\033[0m\n"; } template <typename T> void __print(T x) { cerr << x; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #define debug(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m["; _print(x) #define debug_arr(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m" << (x) << "\033[0m\n" #else #define debug(x...) #define debug_arr(x...) #endif // clang-format on //}}} // clang-format off struct KM { // TODO 0-idx int n, org_n, org_m; LL inf, res; vi matchx, matchy; vector<int> pre; // 连接右集合的左点 vector<bool> visx, visy; // 拜访数组 左右 vector<LL> lx, ly, slack; vector<vector<LL>> g; queue<int> q; KM(int _n, int _m) { org_n = _n, org_m = _m; n = max(_n, _m); inf = numeric_limits<LL>::max(), res = 0; g = vector<vector<LL> >(n, vector<LL>(n)); matchx = vi(n, -1), matchy = vi(n, -1); pre = vi(n); visx = vector<bool>(n), visy = vector<bool>(n); lx = vector<LL>(n, -inf), ly = vector<LL>(n); slack = vector<LL>(n); } void addEdge(int u, int v, LL w) { g[u][v] = max(w, 0ll); } bool check(int v) { visy[v] = true; if (matchy[v] != -1) { q.push(matchy[v]); visx[matchy[v]] = true; // in S return false; } while (v != -1) { matchy[v] = pre[v]; swap(v, matchx[pre[v]]); } return true; } void bfs(int i) { while (!q.empty()) q.pop(); q.push(i), visx[i] = true; while (true) { while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 0; v < n; v++) { if (visy[v]) continue; LL delta = lx[u] + ly[v] - g[u][v]; if (slack[v] >= delta) { pre[v] = u; if (delta) slack[v] = delta; else if (check(v)) return; } } } LL a = inf; for (int j = 0; j < n; j++) if (!visy[j]) a = min(a, slack[j]); for (int j = 0; j < n; j++) { if (visx[j]) lx[j] -= a; // S if (visy[j]) ly[j] += a; // T else slack[j] -= a; // T' } for (int j = 0; j < n; j++) if (!visy[j] && slack[j] == 0 && check(j)) return; } } LL solve() { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) lx[i] = max(lx[i], g[i][j]); for (int i = 0; i < n; i++) { fill(all(slack), inf), fill(all(visx), false), fill(all(visy), false); bfs(i); } for (int i = 0; i < n; i++) { if (g[i][matchx[i]] > 0) res += g[i][matchx[i]]; else matchx[i] = -1; } return res; } }; // clang-format on const int N = 555; int n; int a[N][N]; int main() { #ifdef LOCAL freopen("in", "r", stdin); // freopen("out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(0); while (cin >> n) { auto obj = KM(n, n); LL inf = 1e14; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> a[i][j]; obj.addEdge(i, j, inf - a[i][j]); } } LL ans = n * inf - obj.solve(); cout << ans << endl; for (int i = 0; i < n; ++i) { cout << obj.matchx[i] << " "; } cout << endl; } return 0; }