描述 Description
“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．” Orez 听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez 的羊狼圈可以看作一个 n*m 个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是 Drake 很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以 Orez 决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。 通过仔细观察，Orez 发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。 Orez 想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。
输入格式 InputFormat
文件的第一行包含两个整数 n 和 m。接下来 n 行每行 m 个整数，1 表示该格子属于狼的领地，2 表示属于羊的领地，0 表示该格子不是任何一只动物的领地。
输出格式 OutputFormat
文件中仅包含一个整数 ans，代表篱笆的最短长度。
样例输入 SampleInput
15 17
1 0 1 2 2 1 0 0 1 2 0 2 2 2 0 2 0
2 1 2 2 0 2 1 0 2 2 1 2 2 2 0 2 1
1 1 0 1 1 2 0 2 2 0 0 0 2 0 2 2 2
2 1 2 0 1 1 0 0 1 2 0 1 1 0 2 1 2
2 1 0 0 1 0 0 2 2 1 1 1 2 1 2 0 0
0 1 2 1 2 0 1 0 0 2 0 1 0 0 1 2 2
1 0 1 1 0 1 1 0 1 0 1 2 2 0 2 0 0
2 1 1 0 1 0 1 2 2 2 0 1 2 0 1 2 0
2 1 1 2 1 1 2 2 0 1 2 2 2 0 2 1 2
0 1 2 1 1 1 1 2 2 0 0 0 2 1 1 0 2
0 1 0 2 1 1 1 2 2 1 0 1 1 1 1 0 2
1 1 2 1 1 0 0 1 0 0 2 1 1 2 1 2 2
0 1 0 0 0 2 2 0 0 0 2 2 0 1 0 1 1
0 1 0 0 1 1 0 1 2 0 2 0 1 1 1 0 1
1 1 0 2 2 1 0 0 0 0 1 2 0 1 2 2 0
样例输出 SampleOutput
169
源点与狼建边容量无限，羊与汇点建边容量无限，中间相邻的狼向空点和羊、空点向空点和羊建边容量一，求最小割。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <deque>
using namespace std;
const int inf = 0x7fffffff / 27.11;
const int maxn = 10005;
const int maxm = 5 * maxn;
const int dx[5] = {0, 0, 0, 1, -1};
const int dy[5] = {0, 1, -1, 0, 0};
int i, j, t, n, m, l, r, k, z, y, x;
struct edge
{
int to, fl, nx;
} e[maxm];
int head[maxn], dis[maxn], used[maxn], cur[maxn];
int a[105][105];
int cnt, num;
deque <int> q;
inline void ins(int u, int v, int f)
{
e[cnt] = (edge)
{
v, f, head[u]
}; head[u] = cnt++;
e[cnt] = (edge)
{
u, 0, head[v]
}; head[v] = cnt++;
}
inline bool bfs(int s, int t, int tim)
{
int i, u, v;
while (!q.empty()) q.pop_front();
dis[s] = 0; used[s] = tim;
q.push_back(s);
while (!q.empty())
{
u = q.front(); q.pop_front();
for (i = head[u]; i != -1; i = e[i].nx)
{
v = e[i].to;
if (used[v] != tim && e[i].fl > 0)
{
used[v] = tim;
dis[v] = dis[u] + 1;
q.push_back(v);
}
}
}
return (used[t] == tim);
}
int dfs(int u, int t, int flow)
{
int v, d, f = flow;
if (u == t) return flow;
for (int &i = cur[u]; i != -1; i = e[i].nx)
{
v = e[i].to;
if (dis[v] == dis[u] + 1 && e[i].fl > 0)
{
d = dfs(v, t, min(f, e[i].fl));
e[i].fl -= d; e[i ^ 1].fl += d;
f -= d;
if (f == 0) break;
}
}
return flow - f;
}
inline void dinic(int s, int t)
{
int ans = 0;
while (bfs(s, t, ++num))
{
memcpy(cur, head, sizeof(head));
ans += dfs(s, t, inf);
}
printf("%d\n", ans);
}
int main()
{
cnt = num = 0;
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) scanf("%d", &a[i][j]);
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
if (a[i][j] == 1) ins(0, m * (i - 1) + j, inf);
if (a[i][j] == 2) ins(m * (i - 1) + j, n * m + 1, inf);
if (a[i][j] != 2)
{
for (k = 1; k <= 4; k++)
{
x = i + dx[k]; y = j + dy[k];
if (x <= 0 || y <= 0 || x > n || y > m) continue;
if ((a[i][j] != 2 && a[x][y] != 1)) ins(m * (i - 1) + j, m * (x - 1) + y, 1);
}
}
}
}
dinic(0, m * n + 1);
return 0;
}