网络流24题-洛谷P2774 方格取数问题

题目背景

none!

题目描述

在一个有 m*n 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。

输入输出格式

输入格式:

第 1 行有 2 个正整数 m 和 n,分别表示棋盘的行数和列数。接下来的 m 行,每行有 n 个正整数,表示棋盘方格中的数。

输出格式:

程序运行结束时,将取数的最大总和输出

输入输出样例

输入样例#1:

输出样例#1:

说明

m,n<=100

首先可将棋盘黑白染色,相邻棋盘格子颜色不同。然后就会发现这其实是一个二分图,白点可以分为一个集合\(X\),黑点可以分为另一个集合\(Y\),任意一个点都可视为与其上下左右四个点相连,“任意两个方格没有公共边”,相当于每对相邻的点最多选一个,而要使这样的策略取出来的点权之和最大,其实就是一个最大权独立集问题。

最大权独立集问题是最小权覆盖集问题的对偶,最小权覆盖集又可以用最大流解决。因此,我们可以求最小权覆盖集,然后用所有格子的总和减去它,就是最大权独立集的权值之和了。具体而言,将源点\(S\)与所有黑点以容量为方格中的数的边相连,将所有白点以容量为方格中的数的边与汇点\(T\)相连,对于黑点->相邻白点,连容量为inf的边,跑一遍最大流就是最小权覆盖集的权值了,再用sum相减即可。

具体原理可参见最小割模型在信息学竞赛中的应用

代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*