JMK no matter what

옛날에 했던 구현.

lang:cpp
struct Hungarian
{ 
  int n, result;
  vector<vector<int> > adj;
  vector<int> rowMatch, colMatch;
  vector<bool> seen, rowSelected, colSelected;
  vector<vector<int> > weight;

  operator int () { return result; }

  Hungarian(const vector<vector<int> >& w)
    : n(w.sz), adj(w.sz), rowMatch(w.sz), colMatch(w.sz), seen(w.sz), rowSelected(w.sz), colSelected(w.sz), weight(w)
  {
    REP(i,n) { int min = *min_element(all(weight[i])); REP(j,n) weight[i][j] -= min; }
    REP(i,n) { int min = weight[0][i]; FOR(j,1,n) min <?= weight[j][i]; REP(j,n) weight[j][i] -= min; }

    while (true)
    {   
      REP(i,n) adj[i].clear();
      REP(i,n) REP(j,n) if (weight[i][j] == 0) adj[i].push_back(j);
      if (match() == n) break;
      selectLine();
      int min = 987654321;
      REP(i,n) if(!rowSelected[i]) REP(j,n) if(!colSelected[j]) min <?= weight[i][j];
      REP(i,n) REP(j,n)
      {
        if (rowSelected[i] && colSelected[j]) weight[i][j] += min;
        if (!rowSelected[i] && !colSelected[j]) weight[i][j] -= min;
      }
    }
    result = 0;
    REP(i,n) result += w[i][rowMatch[i]];
  }

  bool augment(int here)
  {
    REP(i,adj[here].sz)
    {
      int there = adj[here][i];
      if (seen[there]) continue; seen[there] = true;
      if (colMatch[there] == -1 || augment(colMatch[there])) { rowMatch[here] = there; colMatch[there] = here; return true; }
    }
    return false;
  }

  int match()
  {
    fill(all(rowMatch), -1); fill(all(colMatch), -1);
    int ret = 0; REP(i,n) { fill(all(seen) ,0); if (augment(i)) ret++; }
    return ret;
  }

  void selectLine()
  {
    vector<int> rq, cq;
    REP(i,n) colSelected[i] = rowSelected[i] = false;
    REP(i,n) if (rowMatch[i] != -1) rowSelected[i] = true; else rq.pb(i);

    while (!rq.empty())
    {
      cq.clear();
      REP(i,rq.sz)
      {
        int here = rq[i];
        REP(there,n)
        {
          if (colSelected[there]) continue;
          if (!weight[here][there] && rowMatch[here] != there)
          {
            colSelected[there] = true;
            cq.push_back(there);
          }
        }
      }
      rq.clear();
      REP(i,cq.sz)
      {
        int here = cq[i];
        if (!rowSelected[colMatch[here]]) continue;
        rowSelected[colMatch[here]] = 0;
        rq.push_back(colMatch[here]);
      }
    }
  }
};