求c语言一道题的题解急急急急急
题目描述Description有一个N×M的单位方格中,其中有些方格是水塘,其他方格是陆地。如果要用1×2的矩阵区覆盖(覆盖过程不容许有任何部分重叠)这个陆地,那么最多可...
题目描述 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 展开
有一个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 展开
展开全部
其实就是一个二分匹配。看这个矩阵
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
应该是可以做的
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
应该是可以做的
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询