二分图的定义：##
二分图的顶点可以被分为两个点集，且相同点集内的顶点之间没有连边
二分图的判定：##
dfs整个图并对其进行染色，且只能染两种颜色，若与其相邻的顶点与其同色则不是二分图，否则继续dfs。
代码：###
//-------------------二分图判定代码：---------------------------//
int dfs(int u){ //染色为1或2
int flag=0;
for(register int v=1;v<=n;v++)
if(u!=v&&g[u][v]) { //如果u和v之间有连边
if(color[v]==0) { //如果v没有染色
color[v]=3-color[u]; //给v染色
flag=dfs(v); //继续dfs
if(!flag)return 0; //如果flag==0说明dfs的结果是非二分图
}
else if(color[u]==color[v]) return 0; //如果染了色且u和v同色则非二分图
}
return 1;
}
二分图的匹配：##
给定一个二分图G，M为G边集的一个子集且满足当中任意的两条边都依附于同一个顶点，则称M是G的一个匹配
在所有匹配中边数最多的称最大匹配
（简单来说就是在二分图里选一些边，让这些边没有公共顶点，从这个角度讲看起来有点像映射）
求二分图最大匹配：##
- 匈牙利算法
- 最大流
最大流就不介绍了因为笔者不会
这里主要介绍匈牙利算法
匈牙利算法：##
匈牙利算法的核心是找增广路。
增广路（或增广轨、交错路）：若P是图G中一条连通两个未匹配顶点的路径，且已匹配边和未匹配边在这条路径上交错出现，则称P是相对于当前匹配M的一条增广路
由增广路的定义，可以推出三个结论 ：
- 结论1：P的路径长度（P内的边数）必定为奇数
证明：由于起点和终点都是未匹配点，所以第一条边和最后一条边一定都是未匹配边，而由定义可以知道匹配边和未匹配边在增广路上交错出现，所以P的路径长度一定为奇数，且未匹配边比匹配边数量多1 - 结论2：P经过取反操作可以得到一个更大的匹配M'
*取反：未匹配边->匹配边，匹配边->未匹配边
从结论1的证明知道未匹配边比匹配边数量证明多1，所以取反得到的匹配边数将比原匹配边数多1 - 结论3：M为G的最大匹配当且仅当不存在相对于M的增广路
反证，如果有的话还可以扩大匹配边数，M就不是G的最大匹配了
所以根据以上三条结论设计出匈牙利算法的流程：
匈牙利算法流程：###
- STEP 1 对于一个没有匹配的顶点u，遍历其每条边，如果这条边上的另一个顶点v还未匹配则说明找到了一个匹配，转STEP 4
- STEP 2 若v已经被匹配，则寻找v的匹配点w，对于w，再遍历其边，找一个未匹配顶点（即反复STEP 1,2 以寻找增广路）
- STEP 3 若在STEP1,2的反复过程中找到一条增广路，修改各自的匹配点并转STEP 4，若未找到增广路则退出
- STEP 4 匹配数++
形象来讲匈牙利算法就是一个找妹子和绿与被绿的过程有机会就上，没机会把原配挤掉也要上，只要你能给原配牵个新妹子
代码：###
我搜了一下，网上流传的大多是邻接矩阵下的匈牙利算法，但邻接矩阵效率较低（尤其在稀疏图上），且空间复杂度较高，所以这里提供一种邻接表的匈牙利算法，其本质是一样的。
//-------------------------匈牙利算法：--------------------------//
int find(int u){
for(register int i=first[u];i;i=nxt[i]) {
int v=to[i];
if(vis[v]) continue;
else {
vis[v]=true;
if(match[v]==-1||find(match[v])) { //如果v未被匹配或从v开始继续寻找找到了一条增广路
match[v]=u;
return 1;
}
}
}
return 0;
}
int hungary(){
for(register int i=1;i<=n;i++){
for(register int j=1;j<=n;j++)vis[j]=false;
ans+=find(i);
}
}
例题及后续拓展走这里：传送门