Submit Info #66218

Problem Lang User Status Time Memory
Assignment Problem cpp hiiragi4000 AC 87 ms 2.37 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.42 MiB
hand_minus_00 AC 85 ms 2.37 MiB
hand_plus_00 AC 87 ms 2.33 MiB
max_random_00 AC 39 ms 2.32 MiB
max_random_01 AC 37 ms 2.32 MiB
max_random_02 AC 36 ms 2.32 MiB
max_random_03 AC 41 ms 2.32 MiB
max_random_04 AC 39 ms 2.32 MiB
random_00 AC 5 ms 0.57 MiB
random_01 AC 6 ms 0.75 MiB
random_02 AC 2 ms 0.50 MiB
random_03 AC 6 ms 0.73 MiB
random_04 AC 1 ms 0.45 MiB

#ifndef MATCHING_HH #define MATCHING_HH #include<algorithm> #include<limits> #include<queue> #include<utility> #include<vector> #include<climits> struct HopcroftKarp{ HopcroftKarp() = default; HopcroftKarp(int l, int r): g(l), mx(l, -1), my(r, -1), lv(l){} void insert_edge(int x, int y){ g[x].push_back(y); } int run(){ int alpha_prime = 0; while(1){ int d = bfs(); if(d == 0){ return alpha_prime; } alpha_prime += d; } } int left_match(int x) const noexcept{ return mx[x]; } int right_match(int y) const noexcept{ return my[y]; } std::pair<std::vector<bool>, std::vector<bool>> min_vertex_cover() const{ std::vector<bool> cx(mx.size()), cy(my.size()), vis(mx.size()); for(int x=0; x<(int)g.size(); ++x) if(mx[x] == -1){ dfs2(vis, x); } for(int x=0; x<(int)g.size(); ++x){ if(!vis[x]){ cx[x] = true; }else{ for(int y: g[x]){ cy[y] = true; } } } return {move(cx), move(cy)}; } private: std::vector<std::vector<int>> g; std::vector<int> mx, my, lv; std::queue<int> q; int bfs(){ fill(lv.begin(), lv.end(), INT_MAX); for(int x=0; x<(int)g.size(); ++x) if(mx[x] == -1){ lv[x] = 0; q.push(x); } int lv_max = INT_MAX; while(!q.empty()){ int x = q.front(); q.pop(); if(lv[x] >= lv_max) continue; for(int y: g[x]){ if(int x2 = my[y]; x2 == -1){ lv_max = std::min(lv_max, lv[x]+1); }else if(lv[x2] == INT_MAX){ lv[x2] = lv[x]+1; q.push(x2); } } } if(lv_max == INT_MAX) return false; int res = 0; for(int x=0; x<(int)g.size(); ++x){ res += mx[x]==-1 && dfs(x, lv_max); } return res; } bool dfs(int x, int lv_max){ if(lv[x] == lv_max) return false; for(int y: g[x]) if(int x2=my[y]; x2==-1 || lv[x2]==lv[x]+1 && dfs(x2, lv_max)){ mx[x] = y; my[y] = x; return true; } lv[x] = INT_MAX; return false; } void dfs2(std::vector<bool> &vis, int x) const{ vis[x] = true; for(int y: g[x]) if(!vis[my[y]]){ dfs2(vis, my[y]); } } }; struct Blossom{ Blossom() = default; explicit Blossom(int n): Blossom(std::vector<std::vector<int>>(n)){} explicit Blossom(std::vector<std::vector<int>> g_ori): g(move(g_ori)), mat(g.size(), -1), b(g.size()), p(g.size()), ce1(g.size()), ce2(g.size()), tag(g.size()), colo(g.size()){} void insert_edge(int u, int v){ g[u].push_back(v); g[v].push_back(u); } bool find_augmenting_path(int s){ if(mat[s] >= 0) return false; fill(b.begin(), b.end(), -1); fill(tag.begin(), tag.end(), 0); fill(colo.begin(), colo.end(), -1); bfs = std::queue<int>(); p[s] = s; colo[s] = 0; bfs.push(s); int n_blos = 0; while(!bfs.empty()){ int u = bfs.front(); bfs.pop(); for(int v: g[u]) if(v!=mat[u] && basis(v)!=basis(u)){ if(colo[v] == -1){ if(mat[v] == -1){ alternate(s, u); mat[u] = v; mat[v] = u; return true; } p[v] = u; colo[v] = 1; p[mat[v]] = v; colo[mat[v]] = 0; bfs.push(mat[v]); }else if(colo[basis(v)] == 0){ int a = lca(n_blos, u, v); contract(u, v, a); contract(v, u, a); } } } return false; } int run(){ int alpha_prime = 0; for(int u=0; u<(int)g.size(); ++u) if(mat[u] == -1){ for(int v: g[u]) if(mat[v] == -1){ mat[u] = v; mat[v] = u; ++alpha_prime; break; } } for(int u=0; u<(int)g.size(); ++u){ alpha_prime += find_augmenting_path(u); } return alpha_prime; } int match(int u) const noexcept{ return mat[u]; } private: std::vector<std::vector<int>> g; std::vector<int> mat, b, p, ce1, ce2, tag; std::queue<int> bfs; std::vector<signed char> colo; int basis(int u){ int r = u; while(b[r] != -1) r = b[r]; for(int v; u!=r; ){ v = b[u]; b[u] = r; u = v; } return r; } void alternate(int s, int t){ if(s == t) return; if(colo[t] == 0){ int u = p[t], v = p[u]; alternate(s, v); mat[u] = v; mat[v] = u; }else{ int u = ce1[t], v = ce2[t]; alternate(mat[t], u); alternate(s, v); mat[u] = v; mat[v] = u; } } int lca(int &n_blos, int u, int v){ u = basis(u); v = basis(v); ++n_blos; while(tag[u] != n_blos){ tag[u] = n_blos; int u2 = basis(p[u]); u = v; v = u2; } return u; } void contract(int u, int v, int a){ for(int i=basis(u); i!=a; i=basis(p[i])){ b[i] = a; if(colo[i] == 1){ ce1[i] = u; ce2[i] = v; bfs.push(i); } } } }; template<typename T> struct Hungarian{ Hungarian() = default; explicit Hungarian(int n): w(n*n), cx(n), cy(n), slack(n), mx(n), my(n), px(n), py(n), sy(n){} int size() const noexcept{ return cx.size(); } T &operator()(int x, int y) noexcept{ return w[x*size()+y]; } T operator()(int x, int y) const noexcept{ return w[x*size()+y]; } T run(){ constexpr T INF = std::numeric_limits<T>::max(); int const n = size(); fill(cy.begin(), cy.end(), 0); fill(my.begin(), my.end(), -1); for(int x=0; x<n; ++x){ cx[x] = *max_element(w.cbegin()+x*n, w.cbegin()+(x+1)*n); } 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){ cx[x2] -= d; } for(int y=0; y<n; ++y){ if(py[y] != -1){ cy[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; } int left_match(int x) const noexcept{ return mx[x]; } int right_match(int y) const noexcept{ return my[y]; } T left_cover(int x) const noexcept{ return cx[x]; } T right_cover(int y) const noexcept{ return cy[y]; } private: std::vector<T> w, cx, cy, slack; std::vector<int> mx, my, px, py, sy; bool dfs(int x){ int const n = size(); for(int y=0; y<n; ++y) if(py[y] == -1){ T d = cx[x]+cy[y]-w[x*n+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]]; } } }; #endif #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.left_match(i), " \n"[i==n-1]); } }