Submit Info #44989

Problem Lang User Status Time Memory
Assignment Problem cpp anachor AC 142 ms 2.68 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 2.55 MiB
hand_minus_00 AC 141 ms 2.55 MiB
hand_plus_00 AC 142 ms 2.59 MiB
max_random_00 AC 38 ms 2.55 MiB
max_random_01 AC 39 ms 2.68 MiB
max_random_02 AC 38 ms 2.68 MiB
max_random_03 AC 41 ms 2.68 MiB
max_random_04 AC 42 ms 2.55 MiB
random_00 AC 7 ms 2.68 MiB
random_01 AC 7 ms 2.68 MiB
random_02 AC 3 ms 2.55 MiB
random_03 AC 6 ms 2.59 MiB
random_04 AC 3 ms 2.59 MiB

#include<bits/stdc++.h> using namespace std; namespace Hungarian { const int nmax1 = 505, nmax2 = 505; long long inf = 1e15; long long matrix[nmax1][nmax2]; long long U[nmax2], V[nmax2], minV[nmax2]; bool used[nmax2]; int match[nmax2], way[nmax2]; void init() { for (int i=0; i<nmax1; i++) for (int j=0; j<nmax2; j++) matrix[i][j] = inf; } void addEdge(int u, int v, long long w) { matrix[u][v] = min(matrix[u][v], w); } long long Hungarian(int x, int y){ fill(U, U+x+1, 0); fill(V, V+y+1, 0); fill(match, match+y+1, 0); fill(way, way+y+1, 0); for(int i = 1; i<=x; i++){ match[0] = i; int lastJ = 0; fill(minV, minV+y+1, inf); fill(used, used+y+1, false); do{ used[lastJ] = true; int lastI = match[lastJ], nextJ; long long delta = inf; for(int j = 1; j<=y; j++){ if(used[j]) continue; long long diffCost = matrix[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<=y; j++){ if(used[j]) U[match[j]] += delta, V[j] -= delta; else minV[j] -= delta; } lastJ = nextJ; } while(match[lastJ] != 0); do{ int prevJ = way[lastJ]; match[lastJ] = match[prevJ]; lastJ = prevJ; } while(lastJ != 0); } return -V[0]; } } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin>>n; Hungarian::init(); for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { int x; cin>>x; Hungarian::addEdge(j, i, x); } } cout<<Hungarian::Hungarian(n, n)<<endl; for (int i=1; i<=n; i++) cout<<Hungarian::match[i]-1<<" "; }