zoj1140匈牙利算法

zoj1140题目的大意是给定一个二分图，求最大匹配数。匈牙利算法就是用来解决二分图最大匹配的问题的算法。

匈牙利算法的思想是不断找增广路（即在匹配中增加一条边）直到无法找到增广路为止。具体实现方式可以用DFS或BFS进行，这里以DFS为例。

假设我们现在有一个左部顶点u，我们尝试将其与所有未匹配的右部顶点v匹配。如果匹配成功，那么我们就得到了一条增广路，否则我们就需要尝试找到与v匹配的左部顶点w，然后再将u与w匹配，这样就可以得到一条更长的增广路。

按照上述方法不断寻找增广路，直到无法找到为止，此时所得到的匹配就是最大匹配。

相关问题

ZOJ1516 Uncle Tom's Inherited Land（二分图最大匹配）

这道题是一个二分图最大匹配的问题，可以使用匈牙利算法来解决。

首先，我们需要将所有的土地分成两组，分别为奇数编号土地和偶数编号土地。如果两块土地之间有边相连，则它们一定是分别属于奇数和偶数编号土地。

接下来，我们需要建立一个二分图模型。将奇数编号土地和偶数编号土地分别看做左右两侧的顶点集合，如果两个土地之间有边相连，则在它们之间连一条边。这样我们就得到了一个二分图。

最后，我们使用匈牙利算法求出该二分图的最大匹配即可。具体实现时，我们从每个未匹配的左侧节点开始，进行深度优先搜索，尝试找到与它相连的右侧节点。如果该右侧节点已经被匹配，则尝试将与该节点匹配的左侧节点找到一个更优的节点。如果找到了这样一个节点，则更新匹配关系，并继续搜索下一个未匹配的左侧节点。如果找不到这样的节点，则返回上一级，尝试从另一个右侧节点开始查找。

最终，匈牙利算法找到的最大匹配数就是可以被继承的土地数量。

代码实现如下：