Submit Info #53509

Problem Lang User Status Time Memory
Assignment Problem cpp WeakestTopology AC 175 ms 2.59 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.70 MiB
hand_minus_00 AC 175 ms 2.59 MiB
hand_plus_00 AC 169 ms 2.59 MiB
max_random_00 AC 40 ms 2.59 MiB
max_random_01 AC 40 ms 2.59 MiB
max_random_02 AC 39 ms 2.58 MiB
max_random_03 AC 41 ms 2.58 MiB
max_random_04 AC 43 ms 2.59 MiB
random_00 AC 6 ms 0.97 MiB
random_01 AC 6 ms 0.96 MiB
random_02 AC 2 ms 0.71 MiB
random_03 AC 6 ms 0.97 MiB
random_04 AC 1 ms 0.71 MiB

#include <bits/stdc++.h> using namespace std; using ll = long long; template<typename T> struct Matching { T cost; // match[v] = matching row to column v (-1 if not matched) vector<int> match; vector<T> ldual, rdual; }; template<typename T> Matching<T> hungarian(const vector<vector<T>>& C) { static const T inf = numeric_limits<T>::max(); int N = (int)size(C), M = (int)size(C[0]); assert(N <= M); vector<int> match(M, -1); vector<T> ldual(N), rdual(M); for (int u = 0; u < N; ++u) { vector<T> dmin(M, inf); vector<int> best(M, -1); vector<bool> vis(M); int last = -1; for (int z = u; z != -1; z = match[last]) { T delta = inf; int next = -1; for (int v = 0; v < M; ++v) { if (vis[v]) continue; T d = C[z][v] - ldual[z] - rdual[v]; if (d < dmin[v]) { dmin[v] = d; best[v] = last; } if (dmin[v] < delta) { delta = dmin[v]; next = v; } } for (int v = 0; v < M; ++v) { if (vis[v]) { ldual[match[v]] += delta; rdual[v] -= delta; } else { dmin[v] -= delta; } } ldual[u] += delta; assert(next != -1); last = next; vis[last] = true; } assert(last != -1); while (best[last] != -1) { match[last] = match[best[last]]; last = best[last]; } match[last] = u; } Matching<T> res{0, match, ldual, rdual}; for (int v = 0; v < M; ++v) { for (int u = 0; u < N; ++u) { assert(ldual[u] + rdual[v] <= C[u][v]); } int u = match[v]; if (u == -1) continue; res.cost += C[u][v]; assert(C[u][v] == ldual[u] + rdual[v]); } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; vector<vector<ll>> A(N, vector<ll>(N)); for (int u = 0; u < N; ++u) { for (int v = 0; v < N; ++v) { cin >> A[v][u]; } } auto res = hungarian(A); cout << res.cost << '\n'; for (int u = 0; u < N; ++u) { int v = res.match[u]; cout << v << "\n "[u + 1 < N]; ll c = res.ldual[v] + res.rdual[u]; } exit(0); }