pku2711.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#include <math.h>
#define SIZE 30
#define X_SIZE 810
#define INF 99999999

char map[SIZE][SIZE];
char liz[SIZE][SIZE];
int id[SIZE][SIZE];
int c[X_SIZE][X_SIZE];
int f[X_SIZE][X_SIZE];
int v[X_SIZE];
int M, N, d, K;
int Q[X_SIZE];

int in_Map(int x, int y)
{
	return x >= 0 && x < N && y >= 0 && y < M;
}

void init()
{
	int i, j;
	scanf("%d %d", &N, &d);
	for (i = 0; i < N; i++)
		scanf("%s", map[i]);
	for (i = 0; i < N; i++)
		scanf("%s", liz[i]);
	M = strlen(map[0]);
	memset(id, -1, sizeof(id));
	memset(c, 0, sizeof(c));
	memset(f, 0, sizeof(f));
	for (i = 0, K = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			if (map[i][j] - '0')
				id[i][j] = K++;
		}
	}
}

void set(int x, int y)
{
	int i, j, k, nx, ny, nk;
	k = id[x][y];
	c[2*k][2*k+1] = map[x][y] - '0';
	if (!in_Map(x-d,y) || !in_Map(x+d,y) || !in_Map(x,y-d) || !in_Map(x,y+d))
	{
		c[2*k+1][2*K] = INF;
	}
	else
	{
		for (i = -d; i <= d; i++)
		{
			for (j = -abs(d - abs(i)); j <= abs(d - abs(i)); j++)
			{
				nx = x + i;
				ny = y + j;
				if (id[nx][ny] != -1)
				{
					nk = id[nx][ny];
					c[2*k+1][nk*2] = map[x][y] - '0';
				}
			}
		}
	}
}

int BFS(int s, int t)
{
	int head, tail, i, p, ans;
	head = 0;
	tail = 1;
	Q[0] = s;
	memset(v, -1, sizeof(v));
	while (head < tail)
	{
		p = Q[head];
		for (i = 0; i < 2 * K + 2; i++)
		{
			if (v[i] == -1 && c[p][i] > f[p][i])
			{
				Q[tail++] = i;
				v[i] = p;
			}
		}
		if (v[t] != -1)
			break;
		head++;
	}
	if (v[t] == -1)
		return 0;
	ans = INF;
	p = t;
	while (p != s)
	{
		if (c[v[p]][p] - f[v[p]][p] < ans)
			ans = c[v[p]][p] - f[v[p]][p];
		p = v[p];
	}
	p = t;
	while (p != s)
	{
		f[v[p]][p] += ans;
		f[p][v[p]] = -f[v[p]][p];
		p = v[p];
	}
	return ans;
}

int maxflow(int s, int t)
{
	int ans = 0, tmp;
	while (1)
	{
		tmp = BFS(s, t);
		if (tmp)
			ans += tmp;
		else
			break;
	}
	return ans;
}

void solve()
{
	int i, j, cnt, ans;
	cnt = 0;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			if (id[i][j] != -1)
				set(i, j);
			if (liz[i][j] == 'L')
			{
				c[2*K+1][2*id[i][j]] = 1;
				cnt++;
			}
		}
	}
	ans = cnt - maxflow(2*K+1, 2*K);
	if (ans == 0)
		printf("no lizard was left behind.\n");
	else if (ans == 1)
		printf("1 lizard was left behind.\n");
	else
		printf("%d lizards were left behind.\n", ans);
}

int main()
{
	int t, T;
	scanf("%d", &T);
	for (t = 1; t <= T; t++)
	{
		init();
		printf("Case #%d: ", t);
		solve();
	}
	return 0;
}