二分图 ： 把无向图G = （V，E）分为两个集合$V_1$和$V_2$，所有的都在$V_1$和$V_2$之间，而$V_1$或$V_2$的内部没有边，$V_1$中的一个点与$V_2$中的一个点关联，称为一个匹配。
一个图是否为二分图可以通过染色法进行判断。染色结束后，如果所有相邻顶点的颜色都不想同，它就是二分图。
- 染色法 用两种颜色对所有顶点进行染色，要求一条边所连接的两个相邻顶点的颜色不相同。
一个图是二分图，当且仅当他不含边的数量为奇数的环。
二分图匹配问题
1. 无权图，求包含边数最多的匹配，即二分图的最大匹配。
2. 带权图，求边权之和尽量大的匹配。使用KM算法。
匈牙利算法
- 增广路 从一个未匹配点出发，依次经过匹配边和非匹配边…到达未匹配点形成的路径叫做增广路
- 匹配 一个包含若干条边的集合，且其中任意两条边没有公共端点
- 最大匹配 包含边数最大的匹配称为最大匹配
百度百科的证明 增广路中匹配边的数量 + 1 等于 非匹配边的数量 证明
算法流程参考 趣写算法系列之–匈牙利算法
证明 ： 最大匹配 与 增广路不存在时充要条件（保证匈牙利算法的正确性）
证明充分条件 ： 最大匹配时，增广路不存在
反证法 ： 如果能找到增光路，则把原先的匹配数量增广（增加了匹配边的数量：发现，可以将所有非匹配边变为匹配状态，将匹配边变为非匹配状态，最后得到的匹配边的数量就会增加）。
这样得到的新的匹配比原先匹配更大，就不是最大匹配，则证明当最大匹配时增广路不存在。
证明必要条件 ：增广路不存在时是最大匹配
反证法 ： 记当前匹配为 M ，存在比M更大的匹配$M_1$,那么，记H为M并$M_1$ - M交$M_1$ ， 由于M和$M_1$都是匹配，所以H只含有交错路和偶数的交错环。由于|$M_1$| > |M| ,那么必存在交错路。那么就找到了M的增广路，与条件增广路不存在相矛盾。
证明 一个点在第一次找增广路时失败，第二次找增广路不可能成功。（保证只需要进行一次遍历集合）
可以同理上面的定理，当A点第一次找增广路不存在时，匹配为M，当A点第二次找增广路存在时，匹配记位$M_1$， 那么如果A点在M中，由于第二次找到了增广路，那么第一次一定能找到 。如果A点没有在M中，那么由于$M_1$中含有A，可以从A点开始找到一条增广路，所以第一次也可以找到增广路 。
时间复杂度分析
n为点的个数，m为边的个数
由于要遍历n个点，遍历每个点时要找一次增广路是线性的m，所以最坏情况下时间复杂度为O（n * m），但实际运行效率很快。
代码实现
例题 861. 二分图的最大匹配
模板题
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std ;
const int N = 510 , M = 1e5 + 100 ;
int h[N],e[M],ne[M],idx ; //使用链式前星记录边
int wath[N] ; //记录匹配的边
bool st[N];
int n1,n2,m ;
void add(int a,int b){ //加边函数
e[idx] = b,ne[idx] = h[a] , h[a] = idx ++ ;
}
bool find(int x){ //从x开始是否等找到一条增广路径
for(int i = h[x] ; ~i ; i = ne[i]){ //遍历边 ，注意这里遍历的边一定是从左部到右部的边（从右部到左部的边记录在wath数组中）
int j = e[i] ;
if(!st[j]){
st[j] = true ;
if( !wath[j] || find(wath[j]) ){ //如果j没有被匹配，或者可以找到从p开始的增广路（不包括之前的遍历过的节点）
wath[j] = x ; //匹配成功，记录匹配
return true ;
}
}
}
return false;
}
int main(){
cin >> n1 >> n2 >>m ;
memset(h,-1,sizeof h) ;
for(int i = 0 ; i < m ; i++){
int a,b ;
cin >> a>> b ;
add(a,b) ; //加边，只需加一个方向即可
}
int res = 0 ;
for(int i = 1; i <= n1; i ++){
memset(st,0,sizeof st) ; //每次找增广路清空是否找过的状态数组
if(find(i)){
res ++ ;
}
}
cout << res <<endl ;
return 0 ;
}
最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集 = 总点数 - 最小路径覆盖
- 最小顶点覆盖是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联，二分图的最小顶点覆盖数=二分图的最大匹配数；
- 最小路径覆盖也称为最小边覆盖，是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图的最小路径覆盖数=|V|-二分图的最大匹配数；
- 最大独立集是指寻找一个点集，使得其中任意两点在图中无对应边。对于一般图来说，最大独立集是一个NP完全问题，对于二分图来说最大独立集=|V|-二分图的最大匹配数。
最小点覆盖：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边
最小割定理是一个二分图中很重要的定理：一个二分图中的最大匹配数等于这个图中的最小点覆盖数。
最小点集覆盖==最大匹配。首先，最小点集覆盖一定>=最大匹配，因为假设最大匹配为n，那么我们就得到了n条互不相邻的边，光覆盖这些边就要用到n个点。现在我们来思考为什么最小点集覆盖一定<=最大匹配。任何一种n个点的最小点集覆盖，一定可以转化成一个n的最大匹配。因为最小点集覆盖中的每个点都能找到至少一条只有一个端点在点集中的边（如果找不到则说明该点所有的边的另外一个端点都被覆盖，所以该点则没必要被覆盖，和它在最小点集覆盖中相矛盾），只要每个端点都选择一个这样的边，就必然能转化为一个匹配数与点集覆盖的点数相等的匹配方案。所以最大匹配至少为最小点集覆盖数，即最小点击覆盖一定<=最大匹配。综上，二者相等。
参考证明 1 y总提高课视频
最小点覆盖
例题 poj 3041
题意是矩阵中右敌人，使用武器每次可以消灭一行或者一列的敌人 。
可以将每一行看作一个点，每一列看作一个点，将i，j有敌人代表i行j列之间连接一条边。
这时敌人代表边，每消灭一个代表从某一个端点发射武器，那么也就转化为了最小点覆盖问题，由于二分图中最小点覆盖等于最大匹配，所以之间求二分图匹配即可。
这里你可能会有疑问，i行，i列，代表的点不都是i么，那么不久会重复了，实际上，可以把i列看作$i_1$,那么虽然数字是一样的，但是含义不一样，可以把行在左边，列在，右边，建图时只使用从行到列的边即可
参考代码
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 510 , M = 1e4 + 100 ;
int n,m;
int match[N] ; //match[i]代表第i列所匹配的行数为
int h[N],e[M],ne[M],idx;
bool st[N] ;
void add(int a,int b){
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
bool find(int u){ //找到u能否匹配到某一列
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(!st[j]){
st[j] = 1 ;
int t = match[j] ;
if(t == 0 || find(t)){
match[j] = u ;
return true ;
}
}
}
return false ;
}
int main(){
cin >> n >> m ;
memset(h,-1,sizeof h) ;
while(m--){
int a,b;
cin >> a >> b ;
add(a,b) ; //注意只用添加从行到列的边，即，只用添加从左集合到右集合的边
}
int res = 0 ;
for(int i = 1 ; i <= n ; i++){ //注意只用枚举左集合
memset(st,0,sizeof st) ; //注意清空
if(find(i)) res ++ ;
}
cout << res << endl ;
return 0;
}
由于题意说任务可以被任意次序执行，那么可以把状态a[i],和状态b[i],当作点，那么题意就是找到最小点覆盖
参考代码 机器任务
最小路径覆盖
poj 3020
题意是给你一个矩阵，使用一些天线覆盖矩阵的点
一，可以将矩阵上的点拆成两部分。将一个点拆成两个点，但是计算时，只按一个就行，最后res要除以2，因为会产生两种相同对称的匹配
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
typedef pair<int,int> pii ;
const int N = 50 ;
int n,m,cnt;
pii match[N][N] ;
char g[N][N];
bool st[N][N] ;
int d[][2] = {0,1,1,0,0,-1,-1,0} ;
bool find(int x,int y){
for(int i = 0 ; i < 4 ; i ++){
int a = x + d[i][0] , b = y + d[i][1] ;
if(a < 1 || a > n || b < 1 || b > m) continue ;
if(st[a][b] || g[a][b] != '*') continue ;
st[a][b] = 1 ;
pii t = match[a][b] ;
if(t.first == 0 || find(t.first,t.second)) {
match[a][b].first = x ;
match[a][b].second = y ;
return true;
}
}
return false ;
}
int main(){
int t ;
cin >> t ;
while(t--){
cin >> n >> m ;
memset(match,0,sizeof match) ;
for(int i = 1 ; i <= n ; i++){
cin >> (g[i] + 1 ) ;
}
cnt = 0 ;
int res = 0 ;
for(int i = 1 ; i <= n; i ++){
for(int j = 1 ; j <= m ; j++){
if(g[i][j] == '*'){
cnt ++ ;
memset(st,0,sizeof st) ;
if(find(i,j)) res ++ ;
}
}
}
cout << cnt - res / 2 << endl ;
}
return 0;
}
二 将行数与列数和为奇数点与偶数点分为不同的集合，这样不需要res/2
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
typedef pair<int,int> pii ;
const int N = 50 ;
int n,m,cnt;
pii match[N][N] ;
char g[N][N];
bool st[N][N] ;
int d[][2] = {0,1,1,0,0,-1,-1,0} ;
bool find(int x,int y){
for(int i = 0 ; i < 4 ; i ++){
int a = x + d[i][0] , b = y + d[i][1] ;
if(a < 1 || a > n || b < 1 || b > m) continue ;
if(st[a][b] || g[a][b] != '*') continue ;
st[a][b] = 1 ;
pii t = match[a][b] ;
if(t.first == 0 || find(t.first,t.second)) {
match[a][b].first = x ;
match[a][b].second = y ;
return true;
}
}
return false ;
}
int main(){
int t ;
cin >> t ;
while(t--){
cin >> n >> m ;
memset(match,0,sizeof match) ;
for(int i = 1 ; i <= n ; i++){
cin >> (g[i] + 1 ) ;
}
cnt = 0 ;
int res = 0 ;
for(int i = 1 ; i <= n; i ++){
for(int j = 1 ; j <= m ; j++){
if(g[i][j] == '*' ){
cnt ++ ;
if((i + j) & 1 ){
memset(st,0,sizeof st) ;
if(find(i,j)) res ++ ;
}
}
}
}
cout << cnt - res << endl ;
}
return 0;
}
