用二分图求zoj1364

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

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

相关问题

zoj 1516（二分图最大匹配）

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

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

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

用python做zoj2212

ZOJ2212 题目描述：

有一个由若干行若干列的矩阵，每个位置上有一个数字，现在要把这个矩阵分成若干个区域，每个区域内部的数字相同，且相邻的区域不能有相同的数字。请你求出最多能将这个矩阵分成多少个区域。

输入：

输入的第一行有两个整数，分别表示矩阵的行数和列数。接下来的若干行中，每行有若干个整数，表示矩阵中的数字。

输出：

输出一个整数，表示最多能将这个矩阵分成多少个区域。

样例输入：

3 3
1 2 3
1 4 5
6 7 8

样例输出：

5

解题思路：

本题可以用深度优先搜索（DFS）或广度优先搜索（BFS）来实现。以 DFS 为例，对每个区域建立一个 visited 数组，表示该区域中的元素是否已被访问过。对于每个未访问过的区域，从该区域中任选一个元素开始进行 DFS，将该区域中的所有元素标记为已访问，并将这个区域中的元素值记为当前搜索的值。继续搜索，直到找不到相邻区域中有相同元素值的区域为止。这样就完成了一个区域的搜索。接着，继续搜索下一个未访问过的区域，直到所有区域都被访问过为止。

代码实现：