夜间模式
字体
阴影
滤镜
主题色
P2774 方格取数问题

题面

洛谷 P2774

题目描述

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

输入格式

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

输出格式

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

思路

把每个格子看做一个点,向相邻的四个格子连边。当前的格子和四周的格子互斥。要让每个格子不与相邻的格子同时选,就是切断它们之间的边。切断边数的最小值就是最小割。

不需要的边割掉后,剩下的就是答案。

把格子黑白相间染色,源点向每一个黑格(或白格)$i$ 连权值为 $a[i]$ 的边,每一个白格(或黑格)$i$ 向汇点连权值为 $a[i]$ 的边,每个黑格(或白格)向相邻的格子连权值为 $+ \infty$ 的边。

跑一遍 Dinic,得到最小割(最大流)为 $ans$,答案即为 $\sum_i\sum_ja\lbrack i\rbrack\lbrack j\rbrack-ans$。

代码

暂无评论

发送评论


				
上一篇
下一篇