Submit Info #40874

Problem Lang User Status Time Memory
Assignment Problem cpp14 (anonymous) AC 200 ms 8.55 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
hand_minus_00 AC 200 ms 8.50 MiB
hand_plus_00 AC 153 ms 8.55 MiB
max_random_00 AC 173 ms 8.49 MiB
max_random_01 AC 147 ms 8.42 MiB
max_random_02 AC 173 ms 8.42 MiB
max_random_03 AC 163 ms 8.49 MiB
max_random_04 AC 174 ms 8.42 MiB
random_00 AC 10 ms 2.42 MiB
random_01 AC 14 ms 2.55 MiB
random_02 AC 3 ms 1.30 MiB
random_03 AC 13 ms 2.55 MiB
random_04 AC 1 ms 0.80 MiB

#include<bits/stdc++.h> #define int long long const int N = 1005; const int inf = 1e18; using namespace std; typedef pair <int, int> ii; struct Hungarian{ vector <ii> G[N]; int n, m, c[2][N], nxt[N], pre[N]; bool visited[2][N]; Hungarian(int n, int m): n(n), m(m) { for (int i = 0; i < n; i++) nxt[i] = -1, c[0][i] = inf; for (int i = 0; i < m; i++) pre[i] = -1, c[1][i] = inf; for (int i = 0; i < n; i++) G[i].clear(); } void add_edge(int u, int v, int cost){ G[u].push_back(ii(v, cost)); c[1][v] = min(c[1][v], cost); } bool dfs(int u){ visited[0][u] = true; for (auto pr: G[u]){ int v = pr.first, cost = pr.second; if (cost != c[0][u] + c[1][v] || visited[1][v] || nxt[u] == v) continue; visited[1][v] = true; if (pre[v] == -1 || dfs(pre[v])){ nxt[u] = v; pre[v] = u; return true; } } return false; } bool find_increment(){ for (int i = 0; i < n; i++) visited[0][i] = false; for (int i = 0; i < m; i++) visited[1][i] = false; for (int i = 0; i < n; i++) { if (nxt[i] == -1 && !visited[0][i]) if (dfs(i)) return true; } return false; } int run(){ int match = 0; while (true){ while (find_increment()) match++; int Min = inf; for (int u = 0; u < n; u++){ if (!visited[0][u]) continue; for (auto pr: G[u]){ int v = pr.first, cost = pr.second; if (visited[1][v]) continue; Min = min(Min, cost - c[0][u] - c[1][v]); } } if (Min == inf) break; for (int u = 0; u < n; u++) if (visited[0][u]) c[0][u] += Min; for (int u = 0; u < m; u++) if (visited[1][u]) c[1][u] -= Min; } int sum = 0; for (int u = 0; u < n; u++){ for (auto pr: G[u]){ int v = pr.first, cost = pr.second; if (v == nxt[u]) { sum += cost; } } } return sum; } vector <int> trace(){ vector <int> mv; for (int i = 0; i < n; i++) mv.push_back(nxt[i]); return mv; } void print(){ cout << "print" << endl; for (int i = 0; i < n; i++) cout << c[0][i] << " "; cout << endl; for (int i = 0; i < n; i++) cout << nxt[i] << " "; cout << endl; for (int i = 0; i < m; i++) cout << c[1][i] << " "; cout << endl; for (int i = 0; i < m; i++) cout << pre[i] << " "; cout << endl; for (int u = 0; u < n; u++){ for (auto pr: G[u]){ int v = pr.first, cost = pr.second; cout << u << " " << v << " " << cost << "\n"; } } cout << "end print" << endl; } }; int n, m, c[1005][1005]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; m = n; Hungarian A(n, m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> c[i][j], A.add_edge(i, j, c[i][j]); int ans = A.run(); cout << ans << "\n"; for (auto v: A.trace()) cout << v << " "; } /* 3 4 3 5 3 5 9 4 1 4 */