匈牙利算法
匈牙利算法解决二分图最大匹配问题。有些地方说KM算法和匈牙利算法互为别称，但好像普遍称其中解决二分图最大匹配的那个算法为匈牙利，解决二分图最佳完美匹配的那个叫KM。
匈牙利算法的核心是寻找交互路径（增广路），即一条从未盖点出发，依次经过非匹配边、匹配边、非匹配边、匹配边……终止于未盖点的路径。说白了，寻找交互路径即寻找一对能互达的未盖点，限制是只能交替走非匹配边、匹配边。交互路径用于改进匹配，其中非匹配边的数量比匹配边多1，它们互换身份，就得到一个匹配数+1的匹配。因为如果这个过程不会使已盖点变成未盖点，并且X集合中只能使出发点变成已盖点，所以从前往后扫一遍就可以了。存在增广路=>不是最大匹配。还可以参考Matrix67的解读。
不是最大匹配=>存在增广路。那么对于某未盖点x0，存在一对(x0, y0)，它们相匹配得到更大的匹配。(x0, y0)之间存在一条未匹配边，(y0, x1)之间是一条匹配边，为了改进匹配，它们必须互换身份。按照那个存在的更大的匹配，未盖点x1寻找着配偶，调整……这个过程必定会终结，即(xn, yn)匹配后，不会有新的未盖点产生。而这个调整的过程，走的就是一条交互路径。
交互路径和网络流的增广路很像，走匹配边，就像走反向弧。
可以用dfs或bfs寻找交互路径，这里给出dfs的实现：
// MAXV：顶点总数的最大值，N：X集合的顶点数，E：邻接表的边数组，fst：邻接表头
#include <cstring>
namespace Hungary {int left[MAXV+1], vis[MAXV+1], cnt;bool cross_path(int x){for (int i = fst[x]; i; i = E[i].next) {int y = E[i].v;if (vis[y] != cnt) {vis[y] = cnt;if (!left[y] || cross_path(left[y])) {left[y] = x;return true;}}}return false;}int Hungary(){memset(left, 0, sizeof(left));memset(vis, 0, sizeof(vis));int a = 0;for (cnt = 1; cnt <= N; ++cnt)if (cross_path(cnt))++a;return a;}
};添加计数器cnt，使得vis数组不用每次增广完都清零。
有一道模板题 POJ 1274。源于USACO。CodeVS上也有，但数据有误。
总是WA。比对自己和别人的实现，发现我的vis标记的是边，大家标记的是顶点，就像平常的dfs。改了就AC了。用USACO的数据对拍（下载到的原数据有误，CodeVS似乎就是用的这些），发现出错在后三组较大的数据，比正确答案小一点。于是自己生成数据。那是一节文科大课，我在机房里生成着随机数。得到了一组N=M=10的好数据，还没来得及看就……停电了……
中午又随机了好一会儿，得到一组N=M=10的数据。无奈规模还是太大，手动模拟不清。
天昏地暗的几天……
终于想到，
1. 我只标记了那些未匹配边，于是导致有些边会重复走。
2. 标记边的效率不会比标记点高。
如果把寻找交互路径，看作在走交互路径的基础上寻找一对未盖点，标记点也是更自然的。
信与信封问题
这个问题有意思。
John先生晚上写了n封信，并相应地写了n个信封将信装好，准备寄出。但是，第二天John的儿子Small
John将这n封信都拿出了信封。不幸的是，Small John无法将拿出的信正确地装回信封中了。将Small John所提供的n封信依次编号为1，2，…，n；且n个信封也依次编号为1，2，…，n。假定Small
John能提供一组信息：第i封信肯定不是装在信封j中。请编程帮助Small John，尽可能多地将信正确地装回信封。
将“第i封信肯定不是装在信封j”取反，建立二分图，“第i封信可能装在信封j”。开始在想，是不是非得有一封只和一个信封相连的信，然后引发一系列连锁反应。写了一个程序，想了组数据，和题解比对了一下，不对。
都说它是匈牙利算法的变形。怎么变呢？匈牙利算法求最大匹配。这道题的最大匹配是完美匹配，求的是哪些匹配边是确定的。一条匹配边是确定的，也就是说，它无可取代。取代了会发生什么？引发矛盾，使得不合题意。这道题隐含的约束是什么？信和信封能建立一一对应。
如果一条匹配边是确定的，它必然包含在所有最大匹配——在本题中即完美匹配——里。随意地求出一组最大匹配，依次删去匹配边、再求最大匹配，如果仍是完美匹配，则此边可有可无；如果不是完美匹配，则此边不可或缺。
删去那条匹配边，其他(2n-2)个点仍处于匹配状态。只须从这条前匹配边的某端点出发找交互路径即可。
不知怎么的，总觉得必须保存初始的完美匹配，于是v1是这样的：
for (int i = 1; i <= n; ++i, ++tm)dfs(i);memcpy(save+1, left+1, sizeof(int)*n);bool ok = false;for (int y = 1; y <= n; ++y, ++tm) {int x = left[y];G[x][y] = false;left[y] = 0;if (!dfs(x)) {envlp[x] = y;ok = true; }G[x][y] = true;memcpy(left+1, save+1, sizeof(int)*n);}想到干脆dfs里只找路，不进行修改了。v2是这样的：
for (int i = 1; i <= n; ++i, ++tm)dfs(i, true);bool ok = false;for (int x = 1; x <= n; ++x, ++tm) {int y = right[x];G[x][y] = false;right[x] = left[y] = 0;if (!dfs(x, false)) {printf("%d %d\n", x, y);ok = true; }G[x][y] = true;left[y] = x;right[x] = y;}看了题解的代码，v3是这样的：
for (int i = 1; i <= n; ++i, ++tm)dfs(i);bool ok = false;for (int x = 1; x <= n; ++x, ++tm) {int y = right[x];G[x][y] = false;right[x] = left[y] = 0;if (!dfs(x)) {printf("%d %d\n", x, y);ok = true;left[y] = x;right[x] = y;}G[x][y] = true;}修改了也无所谓，I don’t care~