Submit Info #61063

Problem Lang User Status Time Memory
Assignment Problem cpp (anonymous) AC 141 ms 2.39 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.42 MiB
hand_minus_00 AC 141 ms 2.32 MiB
hand_plus_00 AC 139 ms 2.32 MiB
max_random_00 AC 39 ms 2.36 MiB
max_random_01 AC 35 ms 2.34 MiB
max_random_02 AC 35 ms 2.32 MiB
max_random_03 AC 40 ms 2.39 MiB
max_random_04 AC 38 ms 2.36 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.70 MiB
random_04 AC 1 ms 0.45 MiB

#include <bits/stdc++.h> using namespace std; #define PII pair<int, int> #define VI vector<int> #define VPII vector<PII> #define LL long long #define LD long double #define f first #define s second #define MP make_pair #define PB push_back #define endl '\n' #define ALL(c) (c).begin(), (c).end() #define SIZ(c) (int)(c).size() #define REP(i, n) for(int i = 0; i < (int)(n); ++i) #define FOR(i, b, e) for(int i = (b); i <= (int)(e); ++i) #define FORD(i, b, e) for(int i = (b); i >= (int)(e); --i) #define ll LL #define st f #define nd s #define pb PB #define mp MP #define eb emplace_back #define siz(c) SIZ(c) const int inf = 1e9+7; const ll INF = 1e18L+7; #define sim template<class n sim, class s> ostream & operator << (ostream &p, pair<n, s> x) {return p << "<" << x.f << ", " << x.s << ">";} sim> auto operator << (ostream &p, n y) -> typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type {int o = 0; p << "{"; for(auto c: y) {if(o++) p << ", "; p << c;} return p << "}";} void dor() {cerr << endl;} sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);} sim, class s> void mini(n &p, s y) {if(p>y) p = y;} sim, class s> void maxi(n &p, s y) {if(p<y) p = y;} #ifdef DEB #define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__) #else #define debug(...) #endif #define I(x) #x " =", (x), " " #define int LL //a[1..n][1..m] - wagi, n<=m, O(n^2*m), znajduje minimalny koszt (masymalny: *-1) //u[0..n], v[0..m] - funkcja potencjalu, p[0..m], ans[0..n] - skojarzenie struct hungarian { // cost = -v[0] int n, m; vector<VI> a; VI u, v, p, way, ans; hungarian(int _n, int _m) : n(_n), m(_m) { #define re(x, y) (x).resize(y + 1) re(a, n); re(u, n); re(v, m); re(p, m); re(way, m), re(ans, n); for (auto &x : a) re(x, m); } void addcost(int v1, int v2, int c) { a[v1][v2] = c; } void solve() { FOR(i, 1, n) { p[0] = i; int j0 = 0; VI minv(m + 1, INF); vector<char> used(m + 1, false); do { used[j0] = true; int i0 = p[j0], delta = inf, j1 = 0; FOR(j, 1, m) { if (!used[j]) { int 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(j, 0, m) { if (used[j]) { u[p[j]] += delta; v[j] -= delta; } else { minv[j] -= delta; } } j0 = j1; } while (p[j0] != 0); do { int j1 = way[j0]; p[j0] = p[j1]; j0 = j1; } while (j0); } FOR(j, 1, m) ans[p[j]] = j; // odzyskiwanie wyniku } }; int n; int32_t main() { scanf("%lld", &n); hungarian match(n, n); FOR(i, 1, n) { FOR(j, 1, n) { int a; scanf("%lld", &a); match.addcost(i, j, a); } } match.solve(); printf("%lld\n", -match.v[0]); FOR(i, 1, n) { printf("%lld ", match.ans[i] - 1); } printf("\n"); }