Submit Info #60627

Problem Lang User Status Time Memory
Assignment Problem cpp (anonymous) AC 146 ms 2.38 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
hand_minus_00 AC 146 ms 2.32 MiB
hand_plus_00 AC 145 ms 2.37 MiB
max_random_00 AC 39 ms 2.36 MiB
max_random_01 AC 36 ms 2.36 MiB
max_random_02 AC 35 ms 2.37 MiB
max_random_03 AC 40 ms 2.38 MiB
max_random_04 AC 38 ms 2.32 MiB
random_00 AC 5 ms 0.70 MiB
random_01 AC 6 ms 0.70 MiB
random_02 AC 2 ms 0.45 MiB
random_03 AC 6 ms 0.76 MiB
random_04 AC 1 ms 0.45 MiB

#include <bits/stdc++.h> using namespace std; const long long INF = 1e18; template<typename T> class Hungarian { public: int n; int m; vector< vector<T> > a; vector<T> u; vector<T> v; vector<int> pa; vector<int> pb; vector<int> way; vector<T> minv; vector<bool> used; T inf; Hungarian(int _n, int _m) : n(_n), m(_m) { assert(n <= m); a = vector<vector<T>>(n, vector<T>(m, INF)); u = vector<T>(n + 1); v = vector<T>(m + 1); pa = vector<int>(n + 1, -1); pb = vector<int>(m + 1, -1); way = vector<int>(m, -1); minv = vector<T>(m); used = vector<bool>(m + 1); inf = INF; } void addEdge(int u, int v, long long c) { a[u][v] = c; } inline void add_row(int i) { fill(minv.begin(), minv.end(), INF); fill(used.begin(), used.end(), false); pb[m] = i; pa[i] = m; int j0 = m; do { used[j0] = true; int i0 = pb[j0]; T delta = INF; int j1 = -1; for (int j = 0; j < m; j++) { if (!used[j]) { T cur = a[i0][j] - u[i0] - v[j]; if (cur < minv[j]) { minv[j] = cur; way[j] = j0; } if (minv[j] < delta) { delta = minv[j]; j1 = j; } } } for (int j = 0; j <= m; j++) { if (used[j]) { u[pb[j]] += delta; v[j] -= delta; } else { minv[j] -= delta; } } j0 = j1; } while (pb[j0] != -1); do { int j1 = way[j0]; pb[j0] = pb[j1]; pa[pb[j0]] = j0; j0 = j1; } while (j0 != m); } inline T current_score() { return -v[m]; } inline T solve() { for (int i = 0; i < n; i++) { add_row(i); } return current_score(); } }; int main() { //freopen("input.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(NULL); int n; cin >> n; Hungarian<long long> hung(n, n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { long long x; cin >> x; hung.addEdge(i, j, x); } } cout << hung.solve() << "\n"; for (int i = 0; i < n; i++) { cout << hung.pa[i] << ' '; } return 0; }