1820. Maximum Number of Accepted Invitations

這題就是匹配問題, 一開始用暴力dfs, 但複雜度為O(n!)太大了會TLE

用匈牙利演算法, 可以將複雜度降至O(N³)

演算法的推導就不詳述了, 簡單來說當一個點碰到他目標的點已經有其他人了, 就是請原本選的人看能不能換一下, 大家都有老婆可以找, 原本的人若找得到其他人, 就同意換老婆

這個證明是可以找到最大匹配值得, 一樣就不在這邊證明了

class Solution {
public:
  static bool dfs(vector<vector<int>> &g, int i, vector<bool> &checked, vector<int> &matching){
    for(int j = 0; j < g[i].size();j++){
      int v = g[i][j];
      if(!checked[v]){
        checked[v] = true;
        if(matching[v] == -1 || dfs(g, matching[v], checked, matching)){
          matching[v] = i;
          matching[i] = v;
          return true;
        }
      }
    }
    return false;
  }

  int maximumInvitations(vector<vector<int>> &grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> g(m + n, vector<int>());
    for(int i =0; i < m;i++){
      for(int j = 0; j < n; j++){
        if(grid[i][j] == 1){
          g[i].push_back(m + j);
          g[m + j].push_back(i);
        }
      }
    }
    vector<int> matching(m + n, -1);

    int res = 0;
    for(int i = 0; i < m; i++){
      if(matching[i] == -1){
         vector<bool> checked(m + n, false);
         if(dfs(g, i, checked, matching)){
           res++;
         }
      }
    }
    return res;
  }
};