本题是HDU 1565的加强版 题目描述：n*m的矩阵，每个位置都有一个正数，一开始你的分数是0，当你取走一个数字时，你的分数增加那个分数。如果你取完数字后，新出现了2个相邻的都是
本题是HDU 1565的加强版
题目描述：n*m的矩阵，每个位置都有一个正数，一开始你的分数是0，当你取走一个数字时，你的分数增加那个分数。如果你取完数字后，新出现了2个相邻的都是空的格子，那么你的分数减少2* ( x & y)，x，y是那两个格子的原始数值。
同时有一些附加条件，有一些格子的数字是必须拿走的。
解题报告：
首先，这种相邻格子的问题都会想到它是一个二分图：
横纵坐标为偶数的在左边，横纵坐标为奇数的在右边。
构图如下：
一个超级原点，和左边的点相连接，容量是其权值。
一个超级汇点，右边的点和其连接，容量是其权值。
如果左边的点x和右边的点y相邻，连接x，y容量为2 * (x & y)
这样的图的最小割的定义是：
一个完整的取数过程中的最小花费。
左边的点x和原点连接表示选x，不连接（切断，割）表示不选x，代价就是x的权值。同理右边的点也是。
如果左边的x和原点连接，右边的y和汇点连接，那么满足割的定义，xy之间如果有边，一定要切断，代价就是2 * (x& y)。
同时，为了满足一定要取一些点的附加条件，只要让那些点和对应的原点或者汇点容量为无穷大就可以了，这样割一定不会割那条无穷大。
综上，答案就是所有点的权值减去上述构图的最小割。（参考http://blog.sina.com.cn/s/blog_64675f540100l4h2.html）