This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "https://judge.yosupo.jp/problem/assignment" #include <bits/stdc++.h> using namespace std; #include "../Matching/Hungarian_short.h" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) long long c[N][N]; int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; REP(i,n) REP(j,n) cin >> c[i][j]; auto [cost, matchL] = Hungarian<long long>(n, n, c); cout << cost << endl; for (int m : matchL) cout << m << ' '; cout << endl; return 0; }
#line 1 "Graph/tests/matching_bipartite_weighted_2.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/assignment" #include <bits/stdc++.h> using namespace std; #line 1 "Graph/Matching/Hungarian_short.h" // Copied from https://judge.yosupo.jp/submission/16114 // // NOTE: // - Min-cost matching // - Index from 0 // // Tested: // - https://oj.vnoi.info/problem/match2 // - https://judge.yosupo.jp/problem/assignment // - https://hochiminh17.kattis.com/problems/engaging // // n = |left side|, m = |right side| // Returns {total weight, matches (from left)} const int N = 1011; template<typename T> pair<T, vector<int>> Hungarian (int n, int m, T c[][N]) { vector<T> v(m), dist(m); vector<int> L(n, -1), R(m, -1); vector<int> index(m), prev(m); auto getc = [&] (int i, int j) {return c[i][j] - v[j];}; iota(index.begin(), index.end(), 0); for (int f = 0; f < n; ++f) { for (int j = 0; j < m; ++j) { dist[j] = getc(f, j), prev[j] = f; } T w = 0; int j, l = 0, s = 0, t = 0; while (true) { if (s == t) { l = s, w = dist[index[t++]]; for (int k = t; k < m; ++k) { j = index[k]; T h = dist[j]; if (h <= w) { if (h < w) t = s, w = h; index[k] = index[t], index[t++] = j; } } for (int k = s; k < t; ++k) { j = index[k]; if (R[j] < 0) goto augment; } } int q = index[s++], i = R[q]; for (int k = t; k < m; ++k) { j = index[k]; T h = getc(i, j) - getc(i, q) + w; if (h < dist[j]) { dist[j] = h, prev[j] = i; if (h == w) { if (R[j] < 0) goto augment; index[k] = index[t], index[t++] = j; } } } } augment: for (int k = 0; k < l; ++k) v[index[k]] += dist[index[k]] - w; int i; do { i = R[j] = prev[j]; swap(j, L[i]); } while (i != f); } T ret = 0; for (int i = 0; i < n; ++i) ret += c[i][L[i]]; return {ret, L}; } #line 7 "Graph/tests/matching_bipartite_weighted_2.test.cpp" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) long long c[N][N]; int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; REP(i,n) REP(j,n) cin >> c[i][j]; auto [cost, matchL] = Hungarian<long long>(n, n, c); cout << cost << endl; for (int m : matchL) cout << m << ' '; cout << endl; return 0; }