题目
点这里看题目；以下是简述
小 N 手上有一个 (N imes M) 的方格图，控制某一个点要付出 (A_{ij}) 的代价，然后某个点如果被控制了，或者他周围的所有点（上下左右）都被控制了，那么他就算是被选择了的。一个点如果被选择了，那么可以得到 (B_{ij}) 的回报，现在请你帮小 N 选一个最优的方案，使得 回报 - 代价 尽可能大。
对于 (100\%) 的数据有 (1le N,Mle 50, 1le A_{ij},B_{ij}le 100) 。
分析
看到有代价，于是不难考虑最小割。
那么以下就认为 (uin S) 表示被控制， (uin T) 表示不被控制。
如果不考虑周围四个的额外情况，我们不难想到一种建图：连接 (Soverset{B_{ij}}{ ightarrow }u) ，连接 (uoverset{A_{ij}}{ ightarrow } T) 。
思考一下额外情况的条件：
- 相邻四个点都被控制。
- 当前点没被控制。
我们希望将它转化成 " 所有点都属于同一个集合 " 的情况。注意到网格图是二分图， " 相邻 " 就对应着跨部边。因此当前点和相邻四个点不可能属于同一个部。参考 圈地计划 ，我们可以反转其中某一部的割的含义，例如，左部中的点 (u) ，变成 (uin S) 代表不被控制， (uin T) 代表被控制。此时就变成了我们需要的情况，可以直接建边了。
小结：
利用二分图性质，反转其中一部的割的含义，可以发现，这是一个很有用的方法。
代码
#include <cstdio>
#define rep( i, a, b ) for( int (i) = (a) ; (i) <= (b) ; (i) ++ )
#define per( i, a, b ) for( int (i) = (a) ; (i) >= (b) ; (i) -- )
const int INF = 0x3f3f3f3f;
const int MAXN = 2e5 + 5, MAXM = 2e5 + 5;
const int MAXS = 55;
template<typename _T>
void read( _T &x )
{
x = 0; char s = getchar(); int f = 1;
while( s < '0' || '9' < s ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ); s = getchar(); }
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
template<typename _T>
void swapp( _T &x, _T &y )
{
_T t = x; x = y, y = t;
}
struct Edge
{
int to, nxt, c;
}Graph[MAXM << 1];
int dir[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
int q[MAXN];
int A[MAXS][MAXS], B[MAXS][MAXS];
int head[MAXN], dep[MAXN], cur[MAXN];
int N, M, cnt = 1, tot;
void AddEdge( const int from, const int to, const int C )
{
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
Graph[cnt].c = C, head[from] = cnt;
}
#define ID( x, y ) ( ( x - 1 ) * M + y )
bool Inside( const int &x, const int &y ) { return 1 <= x && x <= N && 1 <= y && y <= M; }
void AddE( const int from, const int to, const int C ) { AddEdge( from, to, C ), AddEdge( to, from, 0 ); }
bool BFS( const int S, const int T )
{
int h = 1, t = 0, u, v;
for( int i = 1 ; i <= tot ; i ++ ) dep[i] = INF;
dep[q[++ t] = S] = 0;
while( h <= t )
{
u = q[h ++];
for( int i = head[u] ; i ; i = Graph[i].nxt )
if( Graph[i].c && dep[v = Graph[i].to] > dep[u] + 1 )
dep[q[++ t] = v] = dep[u] + 1;
}
return dep[T] < INF;
}
int DFS( const int u, const int lin, const int T )
{
if( u == T ) return lin;
int used = 0, ret, v, c;
for( int &i = cur[u] ; i ; i = Graph[i].nxt )
{
v = Graph[i].to, c = Graph[i].c;
if( dep[v] == dep[u] + 1 && c && ( ret = DFS( v, MIN( lin - used, c ), T ) ) )
{
used += ret, Graph[i].c -= ret, Graph[i ^ 1].c += ret;
if( used == lin ) break;
}
}
if( used < lin ) dep[u] = INF;
return used;
}
int Dinic( const int S, const int T )
{
int f = 0;
while( BFS( S, T ) )
{
for( int i = 1 ; i <= tot ; i ++ ) cur[i] = head[i];
f += DFS( S, INF, T );
}
return f;
}
int main()
{
int ans = 0;
read( N ), read( M ), tot = 2 * N * M;
const int s = ++ tot, t = ++ tot;
rep( i, 1, N ) rep( j, 1, M ) read( A[i][j] );
rep( i, 1, N ) rep( j, 1, M ) read( B[i][j] );
rep( i, 1, N ) rep( j, 1, M )
{
ans += B[i][j] << 1;
int cur = ID( i, j ) + N * M;
if( ( i + j ) & 1 )
{
AddE( cur, t, B[i][j] );
swapp( A[i][j], B[i][j] );
AddE( ID( i, j ), cur, INF );
for( int k = 0, tx, ty ; k < 4 ; k ++ )
if( Inside( tx = i + dir[k][0], ty = j + dir[k][1] ) )
AddE( ID( tx, ty ), cur, INF );
}
else
{
AddE( s, cur, B[i][j] );
AddE( cur, ID( i, j ), INF );
for( int k = 0, tx, ty ; k < 4 ; k ++ )
if( Inside( tx = i + dir[k][0], ty = j + dir[k][1] ) )
AddE( cur, ID( tx, ty ), INF );
}
AddE( s, ID( i, j ), A[i][j] ), AddE( ID( i, j ), t, B[i][j] );
}
write( ans - Dinic( s, t ) ), putchar( '
' );
return 0;
}