「BZOJ1412」[ZJOI2009]狼和羊的故事

Description

“狼爱上羊啊爱的疯狂,谁让他们真爱了一场;狼爱上羊啊并不荒唐,他们说有爱就有方向......” Orez听到这首歌,心想:狼和羊如此和谐,为什么不尝试羊狼合养呢?说干就干! Orez的羊狼圈可以看作一个n×mn\times m个矩阵格子,这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼,它们总是对羊垂涎三尺,那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆,还是要将羊狼分开来养。 通过仔细观察,Orez发现狼和羊都有属于自己领地,若狼和羊们不能呆在自己的领地,那它们就会变得非常暴躁,不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地,再就是篱笆必须修筑完整,也就是说必须修建在单位格子的边界上并且不能只修建一部分。

Input

文件的第一行包含两个整数nnmm
接下来n行每行mm个整数,11表示该格子属于狼的领地,22表示属于羊的领地,00表示该格子不是任何一只动物的领地。

Output

文件中仅包含一个整数ansans,代表篱笆的最短长度。

Sample Input

1
2
3
2 2
2 2
1 1

Sample Output

1
2

HINT

10%10\%的数据 n,m3n,m\leq 3
30%30\%的数据 n,m20n,m\leq 20
100%100\%的数据 n,m100n,m\leq 100

Solution

ss向所有狼连边
所有羊向tt连边。
所有狼或者空白领地向狼连边。
跑最大流。
蔡德仁只能刷水题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 120;
int n, m;
int s, t;
int a[N][N];
struct Edge {
int u, v, nxt, f;
}e[N * N * 4*2];
int head[N*N], en = 1;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en,e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};
int d[N*N];
const int inf = 1e9;
bool bfs() {
for(int i = 1; i <= t; ++i) d[i] = 0;
d[s] = 1;
queue<int>q;
q.push(s);
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f) {
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int k, rest = flow;
for(int i = head[x]; rest && i; i = e[i].nxt) if(d[e[i].v] == d[x] + 1 && e[i].f){
int y = e[i].v;
k = dinic(y, min(rest, e[i].f));
e[i].f -= k;
e[i ^ 1].f += k;
rest -= k;
}
return flow - rest;
}
int main() {
n = read(), m = read();
s = n * m + 1;
t = n * m + 2;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
a[i][j] = read();
if(a[i][j] == 1) addedge(s, (i - 1) * m + j, inf);
else if(a[i][j] == 2)addedge((i - 1) * m + j, t, inf);
}
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(a[i][j] == 1 || a[i][j] == 0) {
for(int k = 0; k < 4; ++k) {
int nx = i + dx[k];
int ny = j + dy[k];
if(nx < 1 || nx > n || ny <1 || ny > m || a[nx][ny] == 1) continue;
addedge((i - 1) *m + j, (nx - 1) * m + ny, 1);
}
}
int y , res = 0;
while(bfs()) while(y = dinic(s, inf)) res += y;
writeln(res);
return 0;
}