题意

给定一个 $n\times m$ 的矩阵，矩阵上每一个点可能是狼、羊或者空地。

你需要在格子的边界修建篱笆，使得任意两个狼与羊的格子不连通。

给一个格子的一条边界修建篱笆，那么篱笆总长度增加 $1$，求篱笆的最短长度。

$n, m\leq 100$.

分析

这是最小割问题的常见模型。

网络流可以用于解决矩阵上，通过限制边，与连通性相关的问题。

这道题，需要把狼和羊分开，所以想到：

源点向所有狼连容量为 $\inf$ 的边；

所有羊向汇点连容量为 $\inf$ 的边；

这样使狼和羊一定分别属于两个集合。

之后对矩阵上的限制进行模拟，所有点向四周连容量为 $1$ 的边。

这样断掉一条边，就等价于在矩阵中选一条边界拦住。

代码

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 10008, MAXM = 1e7;
const int inf = 0x3f3f3f3f;
int n, m, S, T;
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int num[MAXN][MAXN];
int get_id(int x, int y) {
	return (x - 1) * m + y;
}
struct Edge{
	int to, val, nxt;
} edge[MAXM];
int head[MAXN], e_cnt = 1;
void add(int u, int v, int w) {
	edge[++e_cnt] = (Edge){v, w, head[u]};
	head[u] = e_cnt;
}
void add_edge(int u, int v, int w) {
	add(u, v, w); add(v, u, 0);
}
int lev[MAXN];
bool bfs() {
	memset(lev, -1, sizeof(lev)); lev[S] = 0;
	queue<int> q; q.push(S);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int i = head[u]; i; i = edge[i].nxt) {
			int v = edge[i].to, val = edge[i].val;
			if(lev[v] == -1 && val) {
				lev[v] = lev[u] + 1;
				q.push(v);
			}
		}
	}
	return (lev[T] != -1);
}
int dfs(int u, int flow) {
	if(u == T) return flow;
	int ret = 0;
	for(int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to, val = edge[i].val;
		if(lev[v] == lev[u] + 1 && val) {
			int tmp = dfs(v, min(flow, val));
			edge[i].val -= tmp;
			edge[i ^ 1].val += tmp;
			flow -= tmp;
			ret += tmp;
			if(flow == 0) break;
		}
	}
	if(ret == 0) lev[u] = -1;
	return ret;
}
int Dinic() {
	int ret = 0;
	while(bfs()) {
		ret += dfs(S, inf);
	}
	return ret;
}
int main() {
	scanf("%d%d", &n, &m);
	S = 0; T = n * m + 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			scanf("%d", &num[i][j]);
			int id = get_id(i, j);
			if(num[i][j] == 1) add_edge(S, id, inf);
			if(num[i][j] == 2) add_edge(id, T, inf);
			for(int k = 0; k < 4; k++) {
				int nx = i + dir[k][0], ny = j + dir[k][1];
				if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
				add_edge(id, get_id(nx, ny), 1);
			}
		}
	}
	cout << Dinic() << endl;
	return 0;
}