#include <bits/stdc++.h>
using namespace std;

const int oo = 1E9;

#define DELTA(i, j) (weights[i][j] - u[i] - v[j])
#define ALL(a) (a).begin(), (a).end()

int iters = 0;
vector<int> HungarianAlgorithm(const vector<vector<int>>& weights){
  int n = weights.size();
  vector<int> u(n, 0), v(n, 0);
  vector<int> delta(n), delta_pos(n);
  vector<int> perm(n, -1), rev_perm(n, -1);
  vector<char> used_row(n), used_col(n);

  for(int i = 0;i < n;++i){
    fill(ALL(used_row), false);
    fill(ALL(used_col), false);
    used_row[i] = true;

    for(int j = 0;j < n;++j)
      delta[j] = DELTA(i, j),
      delta_pos[j] = i;

    while(true){
      int col = min_element(ALL(delta)) - delta.begin();
      int row = rev_perm[col];
      int val = delta[col];

      for(int i = 0;i < n;++i){
        iters += 1;
        if(used_row[i]) u[i] += val;
        if(used_col[i]) v[i] -= val;
        else delta[i] -= val;
      }

      delta[col] = oo;
      used_col[col] = true;
      if(row >= 0) used_row[row] = true;

      if(row == -1){
        while(col != -1){
          row = delta_pos[col];
          int prev_col = perm[row];
          perm[row] = col;
          rev_perm[col] = row;
          col = prev_col;
        }
        break;
      } else{
        for(int j = 0;j < n;++j)
          if(!used_col[j] && delta[j] > DELTA(row, j))
            delta[j] = DELTA(row, j),
            delta_pos[j] = row;
      }
    }
  }

  return perm;
}

int main(){
  vector<vector<int>> weights = {
      {3, 1, 4},
      {7, 5, 8},
      {2, 1, 3}
  };

  auto perm = HungarianAlgorithm(weights);
  for(int i = 0;i < perm.size();++i)
    cout << i << " -> " << perm[i] << endl;

  return 0;
}