fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define taskname ""
  3. #define ull unsigned long long
  4. #define ll long long
  5. #define db double
  6. #define ld long double
  7. #define fi first
  8. #define se second
  9. #define pii pair<int, int>
  10. #define vii vector<pii>
  11. #define pll pair<ll, ll>
  12. #define vll vector<vll>
  13. #define all(a) (a).begin(), (a).end()
  14. #define foru(i, a, b, k) for(int i = a; i <= b; i+=k)
  15. #define ford(i, a, b, k) for(int i = a; i >= b; i-=k)
  16. #define FOR(i, a, b) for(int i = a; i <= b; i++)
  17. #define pb push_back
  18. #define sz(s) (int)s.size()
  19. #define ctn continue
  20. #define uset unordered_set
  21. #define umap unordered_map
  22. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  23. #define endl "\n"
  24.  
  25. using namespace std;
  26. const int N = 205, INF = 1e9;
  27.  
  28. int n, c[N][N], u[N], v[N], p[N], d[N], trace[N];
  29. bool used[N];
  30.  
  31. int main() {
  32.     if (fopen (taskname".inp", "r")) {
  33.         freopen (taskname".inp", "r", stdin);
  34.         freopen (taskname".out", "w", stdout);
  35.    }
  36.  
  37.     ios_base::sync_with_stdio(false);
  38.     cin.tie(NULL);
  39.  
  40.   cin >> n;
  41.   for (int i = 1; i <= n; ++i) {
  42.     for (int j = 1; j <= n; ++j) {
  43.       cin >> c[i][j];
  44.     }
  45.   }
  46.   for (int i = 1; i <= n; ++i) {
  47.     p[0] = i;
  48.     int j0 = 0;
  49.     fill(d + 1, d + 1 + n, INF);
  50.     fill(used + 1, used + 1 + n, false);
  51.     do {
  52.       used[j0] = true;
  53.       int i0 = p[j0], delta = INF, j1;
  54.       for (int j = 1; j <= n; ++j) {
  55.         if (!used[j]) {
  56.           int cur = c[i0][j] - u[i0] - v[j];
  57.           if (cur < d[j]) {
  58.             d[j] = cur;
  59.             trace[j] = j0;
  60.           }
  61.           if (d[j] < delta) {
  62.             delta = d[j];
  63.             j1 = j;
  64.           }
  65.         }
  66.       }
  67.       for (int j = 0; j <= n; ++j) {
  68.         if (used[j]) {
  69.           u[p[j]] += delta;
  70.           v[j] -= delta;
  71.         } else {
  72.           d[j] -= delta;
  73.         }
  74.       }
  75.       j0 = j1;
  76.     } while (p[j0]);
  77.     do {
  78.       int j1 = trace[j0];
  79.       p[j0] = p[j1];
  80.       j0 = j1;
  81.     } while (j0);
  82.   }
  83.   cout << -v[0] << "\n";
  84.   for (int i = 1; i <= n; ++i) {
  85.     cout << p[i] << " " << i << "\n";
  86.   }
  87.   return (0 ^ 0);
  88. }
  89.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/IGlHKn
language:
C++14 (gcc 8.3)
created:
179 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!