题面
描述
狼爱上羊啊爱的疯狂，谁让他们真爱了一场；
狼爱上羊啊并不荒唐，他们说有爱就有方向……
Orez 听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez 的羊狼圈可以看作一个 n*m 个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是 Drake 很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以 Orez 决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。 通过仔细观察，Orez 发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。 Orez 想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。
输入格式
文件的第一行包含两个整数 n 和 m。接下来 n 行每行 m 个整数，1 表示该格子属于狼的领地，2 表示属于羊的领地，0 表示该格子不是任何一只动物的领地。
输出格式
文件中仅包含一个整数 ans，代表篱笆的最短长度。
思路
考虑建网格图（$(x,y)$ 到 $(x-1,y)$,$(x+1,y)$,$(x,y-1)$,$(x,y+1)$ 建边），要让狼到羊之间无法到达，就是在求一个最小割。
$S$ 到每只狼（或羊）连边，每只狼（或羊）到 $T$ 连边，权值为 $+ \infty$，跑一遍最大流（最大流 = 最小割）。
代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,k,last[200005],to[200005],nextt[200005],s[200005],top=1;
long long v[200005],d[200005];
void add(int a,int b,int c){
nextt[++top]=last[a];
to[top]=b;
s[top]=c;
last[a]=top;
}
bool bfs(long long S,long long T){
memset(v,0,sizeof(v));
memset(d,63,sizeof(d));
queue<long long> q;
q.push(S);
v[S]=1;
d[S]=0;
while (!q.empty()){
long long now=q.front();
q.pop();
v[now]=0;
for (int i=last[now];i;i=nextt[i]){
int j=to[i];
if (d[j]>d[now]&&s[i]){
d[j]=d[now]+1;
if (!v[j]){
q.push(j);
v[j]=1;
}
}
}
}
if (d[T]<1000000000){
return 1;
}
return 0;
}
int dfs(long long x,long long minn,long long T){
if (x==T){
return minn;
}
int now=minn,tmp=0;
for (int i=last[x];i&&now;i=nextt[i]){
int j=to[i];
if (d[j]==d[x]+1&&s[i]){
tmp=dfs(j,min(minn,s[i]),T);
if (tmp){
s[i]-=tmp;
s[i^1]+=tmp;
now-=tmp;
}
}
}
return minn-now;
}
long long dinic(long long S,long long T){
long long ans=0,tmp=0;
while (bfs(S,T)){
while (1){
tmp=dfs(S,2147483647,T);
if (!tmp){
break;
}
ans+=tmp;
}
}
return ans;
}
inline int calc(int x,int y){
return (x-1)*m+y;
}
int main(){
long long S=40005,T=40006;
int a[105][105];
cin>>n>>m;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if (a[i][j]==1){
add(S,calc(i,j),19260817);
add(calc(i,j),S,0);
}
if (a[i][j]==2){
add(calc(i,j),T,19260817);
add(T,calc(i,j),0);
}
if (i<n){
add(calc(i,j),calc(i+1,j),1);
add(calc(i+1,j),calc(i,j),0);
}
if (i>1){
add(calc(i,j),calc(i-1,j),1);
add(calc(i-1,j),calc(i,j),0);
}
if (j<m){
add(calc(i,j),calc(i,j+1),1);
add(calc(i,j+1),calc(i,j),0);
}
if (j>1){
add(calc(i,j),calc(i,j-1),1);
add(calc(i,j-1),calc(i,j),0);
}
}
}
bfs(S,T);
cout<<dinic(S,T);
}
