二分图:左集合的点永远向右集合连边,右集合的点永远向左集合连边,但是集合内不能相互连边

二分图的充分必要条件:至少有两个顶点且没有奇环

二分图的匹配(判断是否有奇环)
1.黑白染色

2.如果是不断加入边,然后判断是否是二分图,用并查集

二分图最大匹配问题:匈牙利算法
算法思路:
1.对于一个男孩子x,如果他喜欢女孩子y,且女孩子y没有舞伴——让他们配对
2.如果y有了舞伴,x还是会去尝试邀请y,如果y发现她的舞伴z可以换一个舞伴,y就主动抛弃掉z(在确定z可以和别人牵手以后),和x成为舞伴
增广路(交错路):通过把原来的匹配边边成非匹配边、非匹配边变成匹配边,使得匹配的边数加一(走的路径是匹配边和非匹配边是交错的)

konig定理:二分图中的最大匹配数等于这个图中的最小点覆盖数
最小点覆盖:每个点覆盖以它为端点的所有边,选择最少的点来覆盖所有的边

图片说明
1.为什么最小点集里点的个数就是等于二分图最大匹配数?因为每个点都是匹配边的一个点。从右边没有匹配过的点出发,按照增广路“交替出现”的要求走(最后走出的路径是很多条不完整的增广路),把所有走过的点标记。那么这些点组成了最小覆盖点集:左边被标记的点,右边没被标记的点(比如左边的6、5、7,右边的1、2、5)。

如果右边的点不是匹配点,那么它早就被当成起点标记了(孤寡点就是起点)
如果左边的那个点是没有匹配过的,那(从起点出发)就走不到那里去(这里一定要理解清楚,如果能走到左边发现这个点没有匹配,相当于找到了一条完整的增广路(边数是奇数,只有一条边都算增广路),不就是匈牙利算法了吗,又多了一条匹配边!)。而一个匹配边不可能左边是标记了的(说明从起点出发经过了这个点),同时右边是没有标记的(不然的话右边的点就能经过这条边到达了,应该是为了说明左边的选出的最小覆盖点和右边的最小覆盖点是不同匹配边的端点)。因此最小点集里的点与匹配边一一对应。

2.为什么这样得到的点集可以覆盖所有的边?因为不可能存在某一条边,它的左端点是没有标记的,而右端点是有标记了(也就是说不可能会漏算)。

二分图最优匹配:KM算法,建立在完美匹配的基础上(可以人为的加边权为0的边,甚至加点来伪造一个完美匹配,即左边每个结点都是匹配点)
图片说明

每个左端点连的权值最大的边视为有效边,左端点的顶标等于有效边的权值,右端点顶标初始为0,只有左顶标+右顶标==边权时,这条边才是有效边。每次找增广路时(dfs(i)),从左端点i出发,把走有效边走过的点标记,如果没找到有效边,在被标记的左端点里找delta=r[u]+l[v]-val[u][v]最小的无效边,通过把被标记的左顶端减delta、标记了的右顶表加delta把这条无效边变成有效边(原来的有效边还是有效边,很妙),然后再去找增广路。
最坏的情况是找n次增广路,每次找增广路最多要修改n次顶标(n次dfs(i)直到直到找到增广路使顶点i匹配成功),每次修改顶标要进行一次类似于匈牙利算法的dfs(i),复杂度最坏情况