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

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

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

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

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

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

代码实现如下：

相关问题

zoj 1516（二分图最大匹配）

这是一道二分图最大匹配问题。二分图是指一个图中的节点可以被分为两个不相交的集合，使得同一个集合中的节点之间没有边相连，而不同集合中的节点之间有边相连。

对于本题，我们可以利用 Hopcroft-Karp 算法进行求解。算法的主要思想是不断增广，通过 BFS 找到增广路径，然后更新匹配情况。

具体实现可以参考以下代码：

用二分图求zoj1364

ZOJ1364可以用二分图匹配算法求解。将所有点按照x坐标从小到大排序，然后对于每一个点，连一条从它向右延伸的线段，线段的长度为从该点到其余所有点的距离中的最小值，表示该点最多延伸到哪里。然后将所有的线段看作左部点，所有的右部点则是原来的点，根据连线是否相交构造二分图。由于匹配的过程中选取的左部点是按照x坐标递增的顺序选取的，所以匹配的结果一定是最优的。最后计算匹配的线段长度之和即为答案。

具体实现细节可以参考下面的代码：