题目链接：
https://www.luogu.org/problemnew/show/P2598
分析：
我们知道此题的目的是将狼和羊分割开，很容易想到狼在S，羊在T中。
首先，我们可以在狼，羊，空地这三者中四连通的连边，流量为1，此时可以表示无篱笆，割一条边就代表建起了长度为1的篱笆。
然后考虑狼如何向S连边呢？
因为狼和S之间的边我们是不能割掉的！
所以把流量赋值为inf即可。
羊和T同理。
然后跑最大流，即为最小割。
代码：
#include<cstdio>
#include<vector>
#include<cstring>
#include<vector>
#include<queue>
#define inf 0x7fffffff
using namespace std;
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
struct edge
{
int to,val,rev;
edge(int _to,int _val,int _rev)
{
to=_to;
val=_val;
rev=_rev;
}
};
vector<edge>e[10005];
void add(int x,int y,int w)
{
e[x].push_back(edge(y,w,e[y].size()));
e[y].push_back(edge(x,0,e[x].size()-1));
}
int s,t;
int d[10005];
bool bfs()
{
queue<int>q;
memset(d,-1,sizeof(d));
d[s]=0;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<e[x].size();i++)
{
int y=e[x][i].to;
if(d[y]==-1&&e[x][i].val)
{
q.push(y);
d[y]=d[x]+1;
}
}
}
if(d[t]==-1)return 0;
return 1;
}
int id[105][105];
int dfs(int x,int low)
{
if(x==t||low==0)return low;
int totflow=0;
for(int i=0;i<e[x].size();i++)
{
int y=e[x][i].to;
int rev=e[x][i].rev;
if(d[y]==d[x]+1&&e[x][i].val)
{
int a=dfs(y,min(low,e[x][i].val));
e[x][i].val-=a;
e[y][rev].val+=a;
low-=a;
totflow+=a;
if(low==0)
return totflow;
}
}
if(low!=0)d[x]=-1;
return totflow;
}
int main()
{
int n,m;
int cnt=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
id[i][j]=++cnt;
}
}
s=0,t=cnt+1;
int a;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a);
if(a==2)
{
add(s,id[i][j],inf);
}
else
if(a==1)
{
add(id[i][j],t,inf);
}
for(int k=1;k<=4;k++)
{
int x=i+dx[k];
int y=j+dy[k];
if(x>0&&x<=n&&y>0&&y<=m)
{
add(id[i][j],id[x][y],1);
}
}
}
}
int ans=0;
while(bfs())
{
ans+=dfs(s,inf);
}
printf("%d",ans);
return 0;
}