Submit Info #44993

Problem Lang User Status Time Memory
Assignment Problem cpp anachor AC 149 ms 2.65 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
hand_minus_00 AC 149 ms 2.59 MiB
hand_plus_00 AC 145 ms 2.55 MiB
max_random_00 AC 40 ms 2.65 MiB
max_random_01 AC 36 ms 2.58 MiB
max_random_02 AC 37 ms 2.59 MiB
max_random_03 AC 41 ms 2.59 MiB
max_random_04 AC 39 ms 2.59 MiB
random_00 AC 5 ms 0.96 MiB
random_01 AC 5 ms 0.99 MiB
random_02 AC 4 ms 0.76 MiB
random_03 AC 6 ms 0.92 MiB
random_04 AC 1 ms 0.71 MiB

/** Hungarian algorithm for minimum weighted bipartite matching. O(n^2 m) For max cost, negate cost matrix and negate output. Everything 1-indexed. Input: (n+1) x (m+1) cost matrix. (0th row and column are useless) Output: (ans, ml), where ml[i] = match for node i on the left. */ #include<bits/stdc++.h> using namespace std; template<typename T> pair<T, vector<int>> Hungarian(const vector<vector<T>> &cost, T INF = 1e15){ int n = cost.size()-1, m = cost[0].size()-1; vector<T> 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<T> minV(m+1, INF); vector<bool> used(m+1); do{ used[lastJ] = true; int lastI = mr[lastJ], nextJ; T delta = INF; for(int j = 1; j<=m; j++){ if(used[j]) continue; T 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<long long>> cost(n+1, vector<long long>(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<<" "; }