首页 > 题解 > bzoj 1324 Exca王者之剑

bzoj 1324 Exca王者之剑

Description

Input

第一行给出数字N,M代表行列数.N,M均小于等于100 下面N行M列用于描述数字矩阵

Output

输出最多可以拿到多少块宝石

Sample Input

2 2

1 2

2 1

Sample Output

4

题解

发现只有偶数的时候才会取,要是奇数的时候取,下次就一定取不到了。

那就转换模型,成了只要一个格子取了,和它相邻的格子就不能取了。

将格子黑白染色,白点连S,黑点连T。而且对于每个白点,和它不能同时取的连上inf的边,表示不能同时割。


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×