蜥蜴

luoguP2472 [SCOI2007]蜥蜴

题目描述

题目链接

在一个 \(r\) 行 \(c\) 列的网格地图中有一些高度不同的石柱，第 \(i\) 行 \(j\) 列的石柱高度为 \(h_{i,j}\)。

一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。

每行每列中相邻石柱的距离为 \(1\)，蜥蜴的跳跃距离是 \(d\)，即蜥蜴可以跳到平面距离不超过 \(d\) 的任何一个石柱上。

石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减 \(1\)（如果仍然落在地图内部，则到达的石柱高度不变）。

如果该石柱原来高度为 \(1\)，则蜥蜴离开后消失，以后其他蜥蜴不能落脚。

任何时刻不能有两只蜥蜴在同一个石柱上。

数据范围：1\(\le r,c\le20\)，\(1\le d\le 4\)，\(1\le h\le 3\)。

解法

首先，观察数据范围，看到不仅 \(h\) 和 \(d\) 很小，而且 \(r\) 和 \(c\) 也很小，所以我们在这里可以用到某些复杂度比较大算法，而且其中的 \(h\) 和 \(d\) 甚至可以当成常数。

然后稍微转化一下题意，要求无法逃离的蜥蜴的最小值，显然就是要求能够逃离的蜥蜴的最大值。

在确定了上面两条做题的小技巧的时候，我们就应该能差不多想到要用最大流了。

考虑建图，先考虑如果说没有高度会降低的限制的话。

对任意一个有蜥蜴的石柱，我们把它连到原点上，边的容量为 \(1\)；然后对于任意一个能够 从当前位置跳出去\(^{[1]}\) 的且有高度的石柱，我们把它连到汇点上，边的容量为 \(INF\)；之后再将每个能够 相互到达\(^{[2]}\) 的石柱所对应的节点相互建边，边容量为 \(INF\)。

接下来考虑如果高度会降低，那么显然一个石柱能够承载的蜥蜴的次数是有限制的，在网络流的模型里就是流过这个点的流量是有限制的，考虑如何将这个限制加入建图。

一种比较经典的点容量转边容量的方法就是拆点，将这个点拆成一个入点和一个出点，入点向出点连容量等于这个点的高度的边，将所有连向这个点的边连向入点，出点连向这个点连向的点。

最后跑最大流就行了。

\([1]\)：对于判断这个能否跳出去，这里给出两种方法，一种是机房同学做的，枚举图上矩阵每一个点，判断横纵坐标加减 \(d\) 是否有跳出界外的。

另一种是我做的，首先我们发现所有能跳出界外的只会是最外面的一圈，且宽度为 \(d\) 的一个空心矩形，我们把这个矩形分成四部分，形成类似于风车的形状。

位于 \(1\) 矩形的横坐标范围是 \([1,c-d]\)，纵坐标是 \([1,d]\)。

位于 \(2\) 矩形的横坐标范围是 \([c-d+1,c]\)，纵坐标是 \([1,r-d]\)。

位于 \(3\) 矩形的横坐标范围是 \([d+1,c]\)，纵坐标是 \([r-d+1,r]\)。

位于 \(4\) 矩形的横坐标范围是 \([1,d]\)，纵坐标是 \([d+1,r]\)。

\([2]\)：对任意两个石柱能否互相到达，这里也给出两种方法，一种是枚举每一个点，再暴力枚举一遍图上的每一个点，看这两个枚举的点是否超过了距离，但是这样这里的建边就会成为整个题的复杂度瓶颈 \(O(n^4)\)。

第二种是我做的，如果先对每个点进行编号，先由左到右，再由上到下依次编号，我们发现对每个点 \((x,y)\) 只要寻找每个点之后的就可以了，然后连上两条双向边。对于判断是否再范围内，如果是同一行就直接连后面的 \(d\) 个，如果不同行就枚举横坐标在 \((x-d,x+d)\) 范围内，纵坐标在 \([y+1,y+d]\) 范围内的即可，枚举量相对于上面那种方法应该是减小了不少。

Code

#include 
#include 
#include 
#include 
using namespace std ;

const int INF = 0x3f3f3f3f ;
int n , m , d , a[25][25] , s , t , dis[805] , ans ;
string ci ;

struct Edge
{
	int nxt , to , len ;
} edge[160005] ;

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

int id ( int i , int j , int op )
{
	return ( i - 1 ) * m + j + op * n * m ;
}

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 = cur [ x ] ; i && res ; i = edge [ i ] .nxt )
	{
		int y = edge [ i ] .to ;
		cur [ x ] = edge [ i ] .nxt ;
		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 main ( )
{
	cin >> n >> m >> d ;
	s = n * m * 2 + 1 ;
	t = s + 1 ;
	for ( int i = 1 ; i <= n ; ++ i )
	{
		cin >> ci ;
		for ( int j = 0 ; j < m ; ++ j )
		{
			a [ i ] [ j + 1 ] = ci [ j ] - '0' ;
			if ( a [ i ] [ j + 1 ] )
				insert ( id ( i , j + 1 , 0 ) , id ( i , j + 1 , 1 ) , a [ i ] [ j + 1 ] ) ,
				insert ( id ( i , j + 1 , 1 ) , id ( i , j + 1 , 0 ) , 0 ) ;
		}
	}
	for ( int i = 1 ; i <= n ; ++ i )
	{
		cin >> ci ;
		for ( int j = 0 ; j < m ; ++ j )
		{
			if ( ci [ j ] == 'L' )
				insert ( s , id ( i , j + 1 , 0 ) , 1 ) ,
				insert ( id ( i , j + 1 , 0 ) , s , 0 ) , ++ ans ;
		}
	}
	if ( n <= d * 2 || m <= d * 2 )
	{
		cout << ans << '\n' ;
		return 0 ;
	}
	for ( int i = 1 ; i <= d ; ++ i )
	{
		for ( int j = 1 ; j <= m - d ; ++ j )
			if ( a [ i ] [ j ] )
				insert ( id ( i , j , 1 ) , t , INF ) ,
				insert ( t , id ( i , j , 1 ) , 0 ) ;
		for ( int j = 1 ; j <= n - d ; ++ j )
			if ( a [ j ] [ m - i + 1 ] )
				insert ( id ( j , m - i + 1 , 1 ) , t , INF ) ,
				insert ( t , id ( j , m - i + 1 , 1 ) , 0 ) ;
		for ( int j = d + 1 ; j <= m ; ++ j )
			if ( a [ n - i + 1 ] [ j ] )
				insert ( id ( n - i + 1 , j , 1 ) , t , INF ) ,
				insert ( t , id ( n - i + 1 , j , 1 ) , 0 ) ;
		for ( int j = d + 1 ; j <= n ; ++ j )
			if ( a [ j ] [ i ] )
				insert ( id ( j , i , 1 ) , t , INF ) ,
				insert ( t , id ( j , i , 1 ) , 0 ) ;
	}
	for ( int i = 1 ; i <= n ; ++ i )
		for ( int j = 1 ; j <= m ; ++ j )
		{
			if ( ! a [ i ] [ j ] )
				continue ;
			for ( int c = j + 1 ; c <= min ( j + d , m ) ; ++ c )
			{
				if ( ! a [ i ] [ c ] )
					continue ;
				insert ( id ( i , j , 1 ) , id ( i , c , 0 ) , INF ) ;
				insert ( id ( i , c , 0 ) , id ( i , j , 1 ) , 0 ) ;
				insert ( id ( i , c , 1 ) , id ( i , j , 0 ) , INF ) ;
				insert ( id ( i , j , 0 ) , id ( i , c , 1 ) , 0 ) ;
			}
			for ( int r = i + 1 ; r <= min ( i + d , n ) ; ++ r )
				for ( int c = max ( 1 , j - d ) ; c <= min ( j + d , m ) ; ++ c )
				{
					if ( ! a [ r ] [ c ] ) continue ;
					if ( ( r - i ) * ( r - i ) + ( c - j ) * ( c - j ) <= d * d )
					{
						insert ( id ( i , j , 1 ) , id ( r , c , 0 ) , INF ) ;
						insert ( id ( r , c , 0 ) , id ( i , j , 1 ) , 0 ) ;
						insert ( id ( r , c , 1 ) , id ( i , j , 0 ) , INF ) ;
						insert ( id ( i , j , 0 ) , id ( r , c , 1 ) , 0 ) ;
					}
				}
		}
	int tmp = 0 ;
	while ( bfs ( ) )
	{
		for ( int i = 1 ; i <= n * m * 2 + 2 ; ++ i )
			cur [ i ] = head [ i ] ;
		while ( tmp = dfs ( s , INF ) )
			ans -= tmp ;
	}
	cout << ans << '\n' ;
	return 0 ;
}