记录编号	399751	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2009] 狼和羊的故事	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.103 s
提交时间	2017-04-27 17:35:42	内存使用	0.50 MiB

//KZNS
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define id(a, b) a*M+b
#define INF 0x7fffffff
#define Pmax 10010
int N, M;
int S, T;
vector<int> gp[Pmax];
vector<int> gto, cap;
int egu;
void adeg(int a, int b, int c = 1) {
	gp[a].push_back(egu++);
	gto.push_back(b);
	cap.push_back(c);

	gp[b].push_back(egu++);
	gto.push_back(a);
	cap.push_back(0);
}
int mv[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void init() {
	int a;
	int x, y;
	scanf("%d %d", &N, &M);
	S = N*M;
	T = N*M+1;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			scanf("%d", &a);
			if (a == 1)
				adeg(S, id(i, j), INF);
			else if (a == 2)
				adeg(id(i, j), T, INF);
			for (int k = 0; k < 4; k++) {
				x = i + mv[k][0];
				y = j + mv[k][1];
				if (0 <= x && x < N && 0 <= y && y < M)
					adeg(id(i,j), id(x,y));
			}
		}
}
int dp[Pmax];
bool BFS() {
	memset(dp, 0, sizeof(dp));
	queue<int> ls;
	ls.push(S);
	dp[S] = 1;
	int x, t, v;
	while (!ls.empty()) {
		x = ls.front();
		ls.pop();
		if (x == T)
			break;
		for (int i = 0; i < (int)gp[x].size(); i++) {
			t = gp[x][i];
			v = gto[t];
			if (!dp[v] && cap[t]) {
				dp[v] = dp[x]+1;
				ls.push(v);
			}
		}
	}
	return dp[T];
}
int cur[Pmax];
int DFS(int x, int mx) {
	if (x == T)
		return mx;
	int t, v;
	int f = 0, dt;
	for (int &i = cur[x]; i < (int) gp[x].size(); i++) {
		t = gp[x][i];
		v = gto[t];
		if (cap[t] && dp[v] == dp[x] + 1) {
			dt = DFS(v, min(cap[t], mx));
			mx -= dt;
			f += dt;
			cap[t] -= dt;
			cap[t^1] += dt;
			if (!mx)
				break;
		}
	}
	return f;
}
void work() {
	int ans = 0;
	while (BFS()) {
		memset(cur, 0, sizeof(cur));
		ans += DFS(S, INF);
	}
	printf("%d\n", ans);
}
int main() {
	freopen("ws.in", "r", stdin);
	freopen("ws.out", "w", stdout);
	init();
	work();
	return 0;
}
//UBWH