题意:在一个有m*n 个方格的棋盘中,每个方格中有一个正整数.现要从方格中取数,使任意2 个数所在方格没有公共边,且取出的数的总和最大.试设计一个满足要求的取数算法. n,m<=30 思路:如果将棋盘黑白点染色,可以发现相邻的黑白点不能同时取 将源点到黑点连一条容量为黑点数字的边,黑点到相邻白点连容量为∞的边,白点到汇点连容量为白点数字的边,可以发现如果不让相邻黑白点同时取到,三条边中必定要切断一条 题意就是让切断的总和最小,所以显然不会切∞,只会切另外两条 跑最小割即可 ..],,,); dy