fork download
copy 
  1. // ~~ icebear love atttt ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int INF = 1e9 + 7;
  6. const int N = 1000 + 5;
  7. int A[N][N];
  8. int n, m;
  9. // https://c...content-available-to-author-only...s.com/graph/hungarian-algorithm.html#the-mathcalon3-algorithm
  10. int main() {
  11.     ios_base::sync_with_stdio(0);
  12.     cin.tie(0); cout.tie(0);
  13.     cin >> n >> m;
  14.     assert(n <= m);
  15.     for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)
  16.         cin >> A[i][j], A[i][j] = -A[i][j];
  17.  
  18.     vector<int> u (n+1), v (m+1), p (m+1), way (m+1);
  19.     for (int i=1; i<=n; ++i) {
  20.         p[0] = i;
  21.         int j0 = 0;
  22.         vector<int> minv (m+1, INF);
  23.         vector<bool> used (m+1, false);
  24.         do {
  25.             used[j0] = true;
  26.             int i0 = p[j0],  delta = INF,  j1;
  27.             for (int j=1; j<=m; ++j)
  28.                 if (!used[j]) {
  29.                     int cur = A[i0][j]-u[i0]-v[j];
  30.                     if (cur < minv[j])
  31.                         minv[j] = cur,  way[j] = j0;
  32.                     if (minv[j] < delta)
  33.                         delta = minv[j],  j1 = j;
  34.                 }
  35.             for (int j=0; j<=m; ++j)
  36.                 if (used[j])
  37.                     u[p[j]] += delta,  v[j] -= delta;
  38.                 else
  39.                     minv[j] -= delta;
  40.             j0 = j1;
  41.         } while (p[j0] != 0);
  42.         do {
  43.             int j1 = way[j0];
  44.             p[j0] = p[j1];
  45.             j0 = j1;
  46.         } while (j0);
  47.     }
  48.  
  49.     vector<int> ans(n + 1);
  50.     for(int j = 1; j <= m; j++) ans[p[j]] = j;
  51.     cout << v[0] << '\n';
  52.     for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
  53.     return 0;
  54. }
  55.  
  56.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/jMhB1B
language:
C++14 (gcc 8.3)
created:
3 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!