Submit Info #60542

Problem Lang User Status Time Memory
Assignment Problem cpp (anonymous) AC 179 ms 4.27 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
hand_minus_00 AC 179 ms 4.15 MiB
hand_plus_00 AC 170 ms 4.26 MiB
max_random_00 AC 87 ms 4.20 MiB
max_random_01 AC 84 ms 4.27 MiB
max_random_02 AC 83 ms 4.26 MiB
max_random_03 AC 89 ms 4.20 MiB
max_random_04 AC 86 ms 4.25 MiB
random_00 AC 11 ms 1.33 MiB
random_01 AC 13 ms 1.50 MiB
random_02 AC 3 ms 0.82 MiB
random_03 AC 13 ms 1.43 MiB
random_04 AC 1 ms 0.45 MiB

#include <bits/stdc++.h> using namespace std; #define MAXN 1010 #define MAXM 1010 #define INF 1000000000 #define INFLL 0x3f3f3f3f3f3f3f3fLL typedef long long ll; // essa versão é indexada em 0 //fazer n <= m // complexidade O(n^2 * m) ll cost[MAXN][MAXM]; vector<ll> pu, pv, par, way; ll n, m; void hungarian(){ pu.assign(n, 0); pv.assign(m+1, 0); way.assign(m+1, m); par.assign(m+1, -1); for(ll i = 0; i < n; i++){ par[m] = i; ll j0 = m; vector<ll> minv(m+1, INFLL); vector<bool> used(m+1, false); do{ used[j0] = true; ll i0 = par[j0], delta = INF, j1; for(ll j = 0; j < m; j++){ if(!used[j]){ ll cur = cost[i0][j] - pu[i0] - pv[j]; if(cur < minv[j]){ minv[j] = cur; way[j] = j0; } if(minv[j] < delta){ delta = minv[j]; j1 = j; } } } for(ll j = 0; j <= m; j++){ if(used[j]){ pu[par[j]] += delta; pv[j] -= delta; } else { minv[j] -= delta; } } j0 = j1; } while(par[j0] != -1); do{ ll j1 = way[j0]; par[j0] = par[j1]; j0 = j1; } while(j0 != m); } } int main(){ cin >> n; m = n; for(ll i = 0; i < n; i++){ for(ll j = 0; j < m; j++){ cin >> cost[i][j]; } } hungarian(); //cout << "total cost: " << -pv[m] << endl; cout << -pv[m] << endl; vector<ll> ans(m); // printar quais foram as opçoes escolhidas // o i é o lado direito que é o lado do m // par[i] é o par dele no lado esquerdo que é o lado do n // e se tiver -1 quer dizer que não tem par for(ll i = 0; i < m; i++){ if(par[i] != -1){ ans[par[i]] = i; //cout << par[i] << " " << i << endl; } } for(auto e : ans) { cout << e << " "; } cout << endl; return 0; }