Submit Info #38750

Problem Lang User Status Time Memory
Assignment Problem cpp hiiragi4000 AC 95 ms 2.61 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
hand_minus_00 AC 95 ms 2.25 MiB
hand_plus_00 AC 94 ms 2.55 MiB
max_random_00 AC 40 ms 2.56 MiB
max_random_01 AC 39 ms 2.55 MiB
max_random_02 AC 38 ms 2.61 MiB
max_random_03 AC 44 ms 2.55 MiB
max_random_04 AC 41 ms 2.49 MiB
random_00 AC 5 ms 0.86 MiB
random_01 AC 6 ms 0.87 MiB
random_02 AC 2 ms 0.67 MiB
random_03 AC 7 ms 0.86 MiB
random_04 AC 1 ms 0.62 MiB

#include<algorithm> #include<limits> #include<vector> template<typename T> struct Hungarian{ Hungarian() = default; explicit Hungarian(int n): n(n), w(n*n), lx(n), ly(n), slack(n), mx(n), my(n), px(n), py(n), sy(n){} T &operator()(int x, int y) noexcept{ return w[n*x+y]; } T run(){ constexpr T INF = std::numeric_limits<T>::max(); fill(ly.begin(), ly.end(), 0); fill(my.begin(), my.end(), -1); for(int x=0; x<n; ++x){ lx[x] = *max_element(w.cbegin()+n*x, w.cbegin()+n*(x+1)); } for(int x=0; x<n; ++x){ fill(slack.begin(), slack.end(), INF); fill(px.begin(), px.end(), -1); fill(py.begin(), py.end(), -1); px[x] = -2; if(dfs(x)){ continue; } while(1){ T d = INF; for(int y=0; y<n; ++y) if(py[y] == -1){ d = std::min(d, slack[y]); } for(int x2=0; x2<n; ++x2) if(px[x2] != -1){ lx[x2] -= d; } for(int y=0; y<n; ++y){ if(py[y] != -1){ ly[y] += d; }else slack[y] -= d; } for(int y=0; y<n; ++y) if(py[y]==-1 && slack[y]==0){ py[y] = sy[y]; if(my[y] == -1){ augment(y); goto next_x; } px[my[y]] = y; if(dfs(my[y])){ goto next_x; } } } next_x:; } T res = 0; for(int y=0; y<n; ++y){ mx[my[y]] = y; res += w[my[y]*n+y]; } return res; } // private: int n = 0; std::vector<T> w, lx, ly, slack; std::vector<int> mx, my, px, py, sy; bool dfs(int x){ for(int y=0; y<n; ++y) if(py[y] == -1){ T d = lx[x]+ly[y]-w[n*x+y]; if(d == 0){ py[y] = x; if(my[y] == -1){ augment(y); return true; } if(px[my[y]] == -1){ px[my[y]] = y; if(dfs(my[y])){ return true; } } }else if(slack[y] > d){ slack[y] = d; sy[y] = x; } } return false; } void augment(int y){ while(y != -2){ my[y] = py[y]; y = px[my[y]]; } } }; #include<cstdio> using namespace std; using i64 = long long; int main(){ int n; scanf("%d", &n); Hungarian<i64> g(n); for(int i=0; i<n; ++i) for(int j=0; j<n; ++j){ int aij; scanf("%d", &aij); g(i, j) = -aij; } printf("%lld\n", -g.run()); for(int i=0; i<n; ++i){ printf("%d%c", g.mx[i], " \n"[i==n-1]); } }