Submit Info #59020

Problem Lang User Status Time Memory
Assignment Problem cpp Nachia AC 1491 ms 10.07 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
hand_minus_00 AC 853 ms 10.07 MiB
hand_plus_00 AC 851 ms 10.03 MiB
max_random_00 AC 1480 ms 10.03 MiB
max_random_01 AC 1491 ms 10.03 MiB
max_random_02 AC 1467 ms 10.07 MiB
max_random_03 AC 1486 ms 10.02 MiB
max_random_04 AC 1460 ms 10.02 MiB
random_00 AC 71 ms 1.70 MiB
random_01 AC 94 ms 1.90 MiB
random_02 AC 9 ms 0.77 MiB
random_03 AC 87 ms 1.82 MiB
random_04 AC 1 ms 0.45 MiB

#include <iostream> #include <vector> #include <algorithm> #include <tuple> using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(n); i++) const i64 INF = 1001001001001001001; pair<vector<i64>,vector<int>> dense_dijkstra(const vector<vector<i64>>& E, const vector<i64>& P, int s){ int n = E.size(); vector<i64> D(n, INF); D[s] = 0; vector<int> pre(n, -1); vector<int> visited(n, 0); int p = s; while(p != -1){ visited[p] = 1; for(int e=0; e<n; e++) if(D[e] > D[p] + P[p] - P[e] + E[p][e]){ pre[e] = p; D[e] = D[p] + P[p] - P[e] + E[p][e]; } int nx = -1; i64 nxd = INF; for(int e=0; e<n; e++) if(visited[e] == 0) if(D[e] < nxd){ nx = e; nxd = D[nx]; } p = nx; } return make_pair(move(D), move(pre)); } vector<int> assignment_problem(const vector<vector<i64>>& A){ int n = A.size(); vector<vector<i64>> E(n*2+2, vector<i64>(n*2+2,INF)); rep(i,n) E[n*2][i] = 0; rep(i,n) E[n+i][n*2+1] = 0; rep(i,n){ i64 mina = INF; rep(j,n) mina = min(mina, A[i][j]); rep(j,n) E[i][n+j] = A[i][j] - mina; } vector<int> ans(n,-1); vector<i64> P(n*2+2,0); rep(t,n){ vector<i64> D; vector<int> pre; tie(D,pre) = dense_dijkstra(E,P,n*2); rep(i,n*2+2) P[i] += D[i]; int p = n*2+1; while(p != n*2){ E[p][pre[p]] = -E[pre[p]][p]; E[pre[p]][p] = INF; if(pre[p] < n) ans[pre[p]] = p-n; p = pre[p]; } } return ans; } int main(){ int N; cin >> N; vector<vector<i64>> A(N,vector<i64>(N,(i64)0)); rep(i,N) rep(j,N) cin >> A[i][j]; auto ans = assignment_problem(A); i64 anscost = 0; rep(i,N) anscost += A[i][ans[i]]; cout << anscost << "\n"; rep(i,N){ if(i) cout << " "; cout << ans[i]; } cout << "\n"; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;