1 匈牙利算法
处理 Bipartite Graph 用的。匈牙利算法主要用来解决两个问题：求二分图的最大匹配数和最小点覆盖数。
匈牙利算法本质上最大化增广路。增广路的数量就是最大匹配的数量。增广路的定义是首尾都是未匹配点的交错路。
注意：二分图是个无向图。
1.1 最大匹配数
class Solution {int m;int n;vector<bool> visr;unordered_map<int, int> mapleft;bool match(vector<vector<int>>& grid, int l) {for (int r = 0; r < n; ++r) {if (!grid[l][r] || visr[r]) continue;visr[r] = true;if (mapleft.find(r) == mapleft.end() || match(grid, mapleft[r])) {mapleft[r] = l;return true;}}return false;}public:int maximumInvitations(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();int ans = 0;for (int i = 0; i < m; ++i) {visr.assign(n, false);if (match(grid, i)) ++ans;}return ans;}
};
注意最后只让左侧的去寻找匹配！
1.2 最小点覆盖
用到König定理：一个二分图中的最大匹配数等于这个图中的最小点覆盖数。
对已经用过匈牙利算法的图的左侧每个未匹配点做一次搜索，左侧未经过点和右侧经过点就是最小点覆盖。直观理解，对于最小点覆盖，某条边的左侧和右侧只要有一个就行。这样算出来它们的并集，刚好是所有匹配边的数量。
1.3 最大独立集
显然的是，最大独立集等于所有顶点减去最小点覆盖。
1.4 经典题目
Muddy Fields
Maximum Students Taking Exam
注意：左右两个集合一定不能有交集，否则不叫二分图。