Question

求c语言一道题的题解急急急急急

题目描述 Description
有一个N×M的单位方格中，其中有些方格是水塘，其他方格是陆地。如果要用1×2的矩阵区覆盖（覆盖过程不容许有任何部分重叠）这个陆地，那么最多可以覆盖多少陆地面积。

输入描述 Input Description
输入文件的第一行是两个整数N，M (1<=N，M<=100)，第二行为一个整数K( K<=50)，接下来的K行，每行两个整数X，Y表示K个水塘的行列位置。(1<=X<=N，1<=Y<=M)。

输出描述 Output Description
输出所覆盖的最大面积块（1×2面积算一块）。
样例输入 Sample Input
4 4
6
1 1
1 4
2 2
4 1
4 2
4 4
样例输出 Sample Output
4

Answer 1

其实就是一个二分匹配。看这个矩阵
1 2 3
4 5 6
7 8 9
可以把：1 3 5 7 9作为1边
2 4 6 8 作为另外一边
然后做一个二分匹配。
i表示行，j表示列，公式表示就是 (i+j)%2 == 0是一边 (i+j)%2 == 1 是另一边
如果发现i,j是水塘，直接跳过就行了，然后对两边的数据进行匹配。
这样单边点的最大个数是5000，显然不能用匈牙利算法 O(n^3)
好久没做题，都忘了Dinic的复杂度。查了一下，用Dinic最大流的思想解决二分匹配的复杂度是 sqrt(V)*E
这道题V最大是5000，E最多是20000，Sqrt(V)*E = 1400000
应该是可以做的