fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define BAI VINH
  6. #define ll long long
  7. #define FIO() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  8. #define open() freopen(BAI".INP","r",stdin); freopen(BAI".OUT","w",stdout);
  9.  
  10. const ll INF = 1e18;
  11.  
  12. ll sol(ll n, const vector<vector<ll>>& vinh) {
  13.     vector<ll> u(n + 1, 0), v(n + 1, 0);
  14.     vector<ll> p(n + 1, 0), way(n + 1, 0);
  15.  
  16.     for (ll i = 1; i <= n; ++i) {
  17.         p[0] = i;
  18.         ll j0 = 0;
  19.         vector<ll> minv(n + 1, INF);
  20.         vector<bool> used(n + 1, false);
  21.  
  22.         do {
  23.             used[j0] = true;
  24.             ll i0 = p[j0], j1 = 0;
  25.             ll delta = INF;
  26.  
  27.             for (ll j = 1; j <= n; ++j) {
  28.                 if (!used[j]) {
  29.                     ll cur = vinh[i0 - 1][j - 1] - u[i0] - v[j];
  30.                     if (cur < minv[j]) {
  31.                         minv[j] = cur;
  32.                         way[j] = j0;
  33.                     }
  34.                     if (minv[j] < delta) {
  35.                         delta = minv[j];
  36.                         j1 = j;
  37.                     }
  38.                 }
  39.             }
  40.  
  41.             for (ll j = 0; j <= n; ++j) {
  42.                 if (used[j]) {
  43.                     u[p[j]] += delta;
  44.                     v[j] -= delta;
  45.                 } else {
  46.                     minv[j] -= delta;
  47.                 }
  48.             }
  49.             j0 = j1;
  50.         } while (p[j0] != 0);
  51.  
  52.         do {
  53.             ll j1 = way[j0];
  54.             p[j0] = p[j1];
  55.             j0 = j1;
  56.         } while (j0 != 0);
  57.     }
  58.     return -v[0];
  59. }
  60.  
  61. int main() {
  62.     FIO();
  63.  
  64.     ll n;
  65.     if (!(cin >> n)) return 0;
  66.  
  67.     vector<vector<ll>> vinh(n, vector<ll>(n));
  68.     for (ll i = 0; i < n; ++i) {
  69.         for (ll j = 0; j < n; ++j) {
  70.             cin >> vinh[i][j];
  71.         }
  72.     }
  73.     cout << sol(n, vinh) << endl;
  74.  
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OfNRU6
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!