圈地计划

luoguP1935 [国家集训队]圈地计划

题目描述

题目链接

最近房地产商 GDOI(Group of Dumbbells Or Idiots) 从 NOI(Nuts Old Idiots) 手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为 \(N\times M\) 块小区域。GDOI 要求将这些区域分为商业区和工业区来开发。根据不同的地形环境，每块小区域建造商业区和工业区能取得不同的经济价值。更具体点，对于第 \(i\) 行第 \(j\) 列的区域，建造商业区将得到 \(A_{i,j}\) 收益，建造工业区将得到 \(B_{i,j}\) 收益。另外不同的区域连在一起可以得到额外的收益，即如果区域 \((i,j)\) 相邻（相邻是指两个格子有公共边）有 \(k\) 块（显然 \(k\) 不超过 \(4\)）类型不同于 \((i,j)\) 的区域，则这块区域能增加 \(k\times C_{i,j}\) 收益。经过 Tiger.S 教授的勘察，收益矩阵 \(A,B,C\) 都已经知道了。你能帮 GDOI 求出一个收益最大的方案么？

数据范围：\(N,M \le 100\)。

解法：

这是一道非常经典的最小割的题目，非常类似于 luoguP1361 小M的作物 这道题。

首先这个题目的收益分成两部分，一部分是建造的收益，一部分是相邻区域的收益。

对于第一部分的收益，我们把每个区域当成一个节点，源点连向这个点的边的容量就是造商业区的收益，这个点的容量连向汇点的边的容量就是造工业区的收益（或者反过来也行）。在最小割中，我们肯定是要对这个点向源点和汇点连的两条边要割掉一条，割掉的那条就是不选的，留下的就是要选择的区。

对于第二部分的收益，我们发现在小M的作物那道题中，我们知道如何求几个结点如果被同时分到源点或者汇点会有额外收益，但是这道题是要求个节点被分到不同的类别会有特殊收益。对于这种问题，我们可以通过一些的手段，将分到不同的类别转换成分到相同的类别，这种手段就是黑白染色。

黑白染色，就是指将任意两个相邻的区间染成不同的颜色，然后对所有相同的颜色是同一种处理方式。

用到此题上就是每个区域和周围四个区域是异色，然后将所有黑色的区域所连的汇点和源点的边的容量反过来，白色保持不动。这样，如果说要使某两个相邻的区域是选择不同的类别，那么他们只要同时选汇点或同时选源点就行了。而且这种方法并不会对第一类的收益产生影响，因为第一类的收益任意两个区域之间相互独立。

最后跑最小割就行了。

Code：

#include 
#include 
#include 
using namespace std ;

#define int long long
const int N = 200005 , INF = 0x3f3f3f3f3f3f3f3f ;
const int dx[] = { 0 , 1 , 0 , -1 } , dy[] = { 1 , 0 , -1 , 0 } ;
int n , m , s , t , ans , dis[N] , wv[105][105] ;

struct Edge
{
	int nxt , to , len ;
} edge[N*20] ;

int cnt = 1 , head[N] ;
void insert ( int u , int v , int w )
{
	edge [ ++ cnt ] .nxt = head [ u ] ;
	edge [ cnt ] .to = v ;
	edge [ cnt ] .len = w ;
	head [ u ] = cnt ;
	ans += w ;
}

queue < int > q ;
bool bfs ( )
{
	memset ( dis , 0 , sizeof ( dis ) ) ;
	dis [ s ] = 1 ;
	q .push ( s ) ;
	while ( ! q .empty ( ) )
	{
		int x = q .front ( ) ; q .pop ( ) ;
		for ( int i = head [ x ] ; i ; i = edge [ i ] .nxt )
		{
			int y = edge [ i ] .to ;
			if ( dis [ y ] || ! edge [ i ] .len )
				continue ;
			dis [ y ] = dis [ x ] + 1 ;
			q .push ( y ) ;
		}
	}
	return dis [ t ] ;
}

int dfs ( int x , int now )
{
	if ( x == t )
		return now ;
	int res = now ;
	for ( int i = head [ x ] ; i && res ; i = edge [ i ] .nxt )
	{
		int y = edge [ i ] .to ;
		if ( dis [ y ] != dis [ x ] + 1 || ! edge [ i ] .len )
			continue ;
		int w = dfs ( y , min ( res , edge [ i ] .len ) ) ;
		if ( ! w ) dis [ y ] = -1 ;
		edge [ i ] .len -= w ;
		edge [ i ^ 1 ] .len += w ;
		res -= w ;
	}
	return now - res ;
}

int id ( int x , int y )
{
	return ( x - 1 ) * m + y ;
}

signed main ( )
{
	cin >> n >> m ;
	s = n * m + 1 ;
	t = s + 1 ;
	for ( int i = 1 ; i <= n ; ++ i )
		for ( int j = 1 ; j <= m ; ++ j )
		{
			int x ;
			cin >> x ;
			if ( ( i + j ) & 1 )
				insert ( s , id ( i , j ) , x ) ,
				insert ( id ( i , j ) , s , 0 ) ;
			else
				insert ( id ( i , j ) , t , x ) ,
				insert ( t , id ( i , j ) , 0 ) ;
		}
	for ( int i = 1 ; i <= n ; ++ i )
		for ( int j = 1 ; j <= m ; ++ j )
		{
			int x ;
			cin >> x ;
			if ( ( i + j ) & 1 )
				insert ( id ( i , j ) , t , x ) ,
				insert ( t , id ( i , j ) , 0 ) ;
			else
				insert ( s , id ( i , j ) , x ) ,
				insert ( id ( i , j ) , s , 0 ) ;
		}
	for ( int i = 1 ; i <= n ; ++ i )
		for ( int j = 1 ; j <= m ; ++ j )
			cin >> wv [ i ] [ j ] ;
	for ( int i = 1 ; i <= n ; ++ i )
		for ( int j = 1 ; j <= m ; ++ j )
			for ( int c = 0 ; c < 2 ; ++ c )
			{
				int ii = i + dx [ c ] , jj = j + dy [ c ] ;
				if ( ii < 1 || jj < 1 || ii > n || jj > m )
					continue ;
				insert ( id ( i , j ) , id ( ii , jj ) , wv [ i ] [ j ] + wv [ ii ] [ jj ] ) ;
				insert ( id ( ii , jj ) , id ( i , j ) , wv [ i ] [ j ] + wv [ ii ] [ jj ] ) ;
				ans -= wv [ i ] [ j ] + wv [ ii ] [ jj ] ;
			}
	int tmp = 0 ;
	while ( bfs ( ) )
		while ( tmp = dfs ( s , INF ) )
			ans -= tmp ;
	cout << ans << '\n' ;
	return 0 ;
}