Submit Info #44991

Problem Lang User Status Time Memory
Assignment Problem cpp anachor AC 151 ms 2.59 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
hand_minus_00 AC 151 ms 2.55 MiB
hand_plus_00 AC 149 ms 2.56 MiB
max_random_00 AC 39 ms 2.59 MiB
max_random_01 AC 38 ms 2.55 MiB
max_random_02 AC 35 ms 2.55 MiB
max_random_03 AC 41 ms 2.55 MiB
max_random_04 AC 39 ms 2.55 MiB
random_00 AC 5 ms 0.93 MiB
random_01 AC 8 ms 1.02 MiB
random_02 AC 2 ms 0.70 MiB
random_03 AC 6 ms 1.02 MiB
random_04 AC 1 ms 0.68 MiB

#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL INF = 1e15; pair<LL, vector<int>> Hungarian(const vector<vector<LL>> &cost){ int n = cost.size()-1, m = cost[0].size()-1; vector<LL> U(n+1), V(n+1); vector<int> mr(m+1), way(m+1), ml(n+1); for(int i = 1; i<=n; i++){ mr[0] = i; int lastJ = 0; vector<LL> minV(m+1, INF); vector<bool> used(m+1); do{ used[lastJ] = true; int lastI = mr[lastJ], nextJ; LL delta = INF; for(int j = 1; j<=m; j++){ if(used[j]) continue; LL diffCost = cost[lastI][j] - U[lastI] - V[j]; if(diffCost < minV[j]) minV[j] = diffCost, way[j] = lastJ; if(minV[j] < delta) delta = minV[j], nextJ = j; } for(int j = 0; j<=m; j++){ if(used[j]) U[mr[j]] += delta, V[j] -= delta; else minV[j] -= delta; } lastJ = nextJ; } while(mr[lastJ] != 0); do{ int prevJ = way[lastJ]; mr[lastJ] = mr[prevJ]; lastJ = prevJ; } while(lastJ != 0); } for (int i=1; i<=m; i++) ml[mr[i]] = i; return {-V[0], ml} ; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin>>n; vector<vector<LL>> cost(n+1, vector<LL>(n+1)); for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cin>>cost[i][j]; auto [ans, match] = Hungarian(cost); cout<<ans<<endl; for (int i=1; i<=n; i++) cout<<match[i]-1<<" "; }