对于二分图匹配的题目，我之前一直都是用网络流解决的，但是，二分图匹配的其它算法也有着自己的特点，在解决图的匹配问题时有时能够更简洁，更灵活，这些算法有时也能给我们解题带来启发。
二分图最大匹配
二分图最大匹配的常用算法是匈牙利算法，代码非常简洁：
int find(int k){
for(int p=head[k];p;p=next[p])if(!used[to[p]]){
used[to[p]]=1;
if(!solver[to[p]]||find(match[to[p]])){
match[to[p]]=k;
return to[p];
}
}
return 0;
}find函数的作用就是在不使之前已经匹配了的点不再匹配的情况下，尝试对这个点进行匹配。 每次find是O(m)的，对每个点都find一次，时间复杂度O(nm)。
例1：HDU3729
有n(n<=60)个人，第i个人说自己的排名\(\in [X_i,Y_i] (X_i,Y_i<=10^5)\) ，求出一个方案使得说真话的人尽量多，从小到大输出每个说真话的人，如果有多个方案，输出字典序最大的。 直接建图？边太多，点也太多。实际上不需要把每个点和边都建出来，只要find每个人，匹配的时候从(X_i到Y_i)尝试就行了。因为每个人最多尝试n条边，所以时间复杂度\(O(n^3)\)。还要保证字典序最大，利用find函数不会使之前点不匹配的特性，从第n个人开始尝试匹配就行了。虽然这题用网络流也不是不行，但必须对网络流的算法流程作很多修改，感觉不如直接匈牙利算法优美。
例2：POJ3715
一个二分图，求其最小覆盖集，按照从小到大的顺序输出，如果有多种方案，输出字典序最小的。 我们知道最小覆盖数=最大匹配数，但覆盖方案与匹配方案之间没有明显的关系。我们考虑每次尝试删除每个点，求出剩下的点的最小覆盖数，如果正好比删除前少一个，那么就可以删除这个点。考虑如何快速的求删除一个点后的最大匹配，只要找到原本这个点匹配的点，find它一下就好了。
例3：BZOJ2437
可以证明空格子走的路径不会经过同一个点两次。像这种在棋盘上走的，不能经过走过的点的博弈问题，都可以从匹配的方向思考。
二分图带权匹配
二分图带权匹配的经典算法是KM算法。网络上对于KM算法的介绍大部分都有一个错误，都说KM算法的时间复杂度是\(O(n^3)\)的，然而他们的代码其实都是\(O(n^4)\)的。我们每次修改顶标后不应该重新find一次，而应该bfs扩展交错树，这样才是\(O(n^3)\)的。代码见UOJ#80。
例1：BZOJ2539
二分图带权匹配裸题，但对于初学者有一个很坑的地方。KM算法求的是完备匹配下的最大权匹配，一般都会把没有连边的点对都连上权值为0的边，这样就可以求最大匹配了，但这样求出来的最大匹配就不一定是完备匹配了。而这题要求的是完备匹配，所以不能连权值为0的边，应该连权值为\(-\infty\)的边。
例2：BZOJ1937
这道题体现了KM算法对解题可以带来启发。可以发现我们一定会增加非树边的权值，降低树边的权值，设原权值为w，更改的权值为d。对于一个非树边i，如果一个树边j在（i的两个端点在树上的路径）上，那么必须保证\(w_i+d_i>=w_j-d_j\)，即\(d_i+d_j>=w_j-w_i\)，可以发现这个跟KM算法中的顶标很像，思考一下就能发现答案就是二分图最大权匹配了。
一般图最大匹配
带花树算法，算法还是比较好理解的，代码也不是很长。一般图最大匹配的题比较少，但建图都非常妙。
例1：UOJ171
每个筐拆成3个点，每个球向它能放的筐的3个点都连边，一个筐的3个点之间互相连边。这样发现如果一个筐是半空的，那么它的3个点就能找到一个匹配。
例2：ZOJ3316
如果有完备匹配，那么后手每次选先手选的点的匹配点就一定能赢。如果没有，先手先选一个没有匹配的点，那后手选的点一定是有匹配的，然后先手再选后手选的点的匹配点，发现这个过程跟找增广路的过程一样，由于是最大匹配，所以找不到长度为奇数的增广路，所以先手必胜。
一般图带权匹配
感觉非常可怕，uoj上只有3个人AC了，而且代码都超长，先不管它了。。。
一些最大最小之间的关系
最大独立集+最小覆盖集=所有节点
最大团=补图的最大独立集
二分图的最大匹配=最小覆盖数