【bzoj2150】部落战争有上下界最小流

题目描述

lanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。 A国是一个M*N的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队，他们约定： 1. 每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。 2. 如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。 3. 每支军队都可以在任意一个城镇停止征战。 4. 所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走1*2的路线，而他们只能走R*C的路线。 lanzerb的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮lanzerb算算至少要多少支军队才能完成统一全国的大业。

输入

第一行包含4个整数M、N、R、C，意义见问题描述。接下来M行每行一个长度为N的字符串。如果某个字符是'.'，表示这个地方是城镇；如果这个字符时'x'，表示这个地方是高山深涧。

输出

输出一个整数，表示最少的军队个数。

样例输入

【样例输入一】
3 3 1 2
...
.x.
...
【样例输入二】
5 4 1 1
....
..x.
...x
....
x...

样例输出

【样例输出一】
4
【样例输出二】
5

题解

很容易看出来的有上下界最小流

将每个点拆成两个，设为xi和yi。S（代码中的b）->xi，容量为1，yi->T，容量为1，xi->yi，容量下界为1，上界为1。

若点i能够到达点j，则yi->xj，容量为1。

这个图的最小流即为答案。

再具体一些的最小流转化为最大流的方法：

S->xi，容量为1，yi->T，容量为1；若点i能够到达点j，则yi->xj，容量为1；

建立超级源汇SS和TT（代码中的s和t），SS->yi，容量为1，xi->TT，容量为1；

T->S，容量为inf。

从SS到TT跑最大流，记录T->S的边的流量（即反向边的残量）为ans1。

然后删除所有与SS或TT相连的边，删除T->S的边，从T到S跑最大流，记为ans2。

ans1-ans2即为答案。

注意往下走是行数增加而不是列数增加，不要弄混。

#include <cstdio>

#include <cstring>

#include <queue>

#define N 6000

#define M 200000

#define inf 0x7fffffff

#define pos(i , j , k) k * n * m + (i - 1) * m + j

using namespace std;

queue<int> q;

int map[60][60] , head[N] , to[M] , val[M] , next[M] , cnt = 1 , s , t , dis[N];

char str[60];

void add(int x , int y , int z)

{

	to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt;

	to[++cnt] = x , val[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt;

}

bool bfs()

{

	int x , i;

	memset(dis , 0 , sizeof(dis));

	while(!q.empty()) q.pop();

	dis[s] = 1 , q.push(s);

	while(!q.empty())

	{

		x = q.front() , q.pop();

		for(i = head[x] ; i ; i = next[i])

		{

			if(val[i] && !dis[to[i]])

			{

				dis[to[i]] = dis[x] + 1;

				if(to[i] == t) return 1;

				q.push(to[i]);

			}

		}

	}

	return 0;

}

int dinic(int x , int low)

{

	if(x == t) return low;

	int temp = low , i , k;

	for(i = head[x] ; i ; i = next[i])

	{

		if(val[i] && dis[to[i]] == dis[x] + 1)

		{

			k = dinic(to[i] , min(temp , val[i]));

			if(!k) dis[to[i]] = 0;

			val[i] -= k , val[i ^ 1] += k;

			if(!(temp -= k)) break;

		}

	}

	return low - temp;

}

int main()

{

	int n , m , r , c , i , j , b , e , ans = 0;

	scanf("%d%d%d%d" , &n , &m , &r , &c) , b = 0 , e = 2 * n * m + 1 , s = 2 * n * m + 2 , t = 2 * n * m + 3;

	add(e , b , inf);

	for(i = 1 ; i <= n ; i ++ )

	{

		scanf("%s" , str + 1);

		for(j = 1 ; j <= m ; j ++ ) map[i][j] = (str[j] == '.');

	}

	for(i = 1 ; i <= n ; i ++ )

	{

		for(j = 1 ; j <= m ; j ++ )

		{

			if(map[i][j])

			{

				add(b , pos(i , j , 0) , 1) , add(pos(i , j , 1) , e , 1) , add(s , pos(i , j , 1) , 1) , add(pos(i , j , 0) , t , 1);

				if(i + r <= n && j + c <= m && map[i + r][j + c]) add(pos(i , j , 1) , pos(i + r , j + c , 0) , 1);

				if(i + r <= n && j - c >= 1 && map[i + r][j - c]) add(pos(i , j , 1) , pos(i + r , j - c , 0) , 1);

				if(i + c <= n && j + r <= m && map[i + c][j + r]) add(pos(i , j , 1) , pos(i + c , j + r , 0) , 1);

				if(i + c <= n && j - r >= 1 && map[i + c][j - r]) add(pos(i , j , 1) , pos(i + c , j - r , 0) , 1);

			}

		}

	}

	while(bfs()) dinic(s , inf);

	ans = val[3];

	for(i = head[s] ; i ; i = next[i]) val[i] = val[i ^ 1] = 0;

	for(i = head[t] ; i ; i = next[i]) val[i] = val[i ^ 1] = 0;

	val[2] = val[3] = 0 , s = e , t = b;

	while(bfs()) ans -= dinic(s , inf);

	printf("%d\n" , ans);

	return 0;

}

巴特西

【bzoj2150】部落战争有上下界最小流

最新文章

热门文章

巴特西

【bzoj2150】部落战争 有上下界最小流

最新文章

热门文章

【bzoj2150】部落战争有上下界最小流