题目链接： https://www.luogu.com.cn/problem/P2598 思路来源博客： https://www.luogu.com.cn/blog/a23333/solution-p2598 算法：1：最大流 最小割 Dinic算法 思路： 建图方式： 1、原点向所有
题目链接：
https://www.luogu.com.cn/problem/P2598
思路来源博客：
https://www.luogu.com.cn/blog/a23333/solution-p2598
算法：1：最大流 最小割 Dinic算法
思路：
建图方式：
1、原点向所有狼连流量 inf的边
2、所有羊向汇点连流量 inf 的边
3、所有点向四周连流量为1的边
然后下面就没了，求出最小割就是答案，不用考虑题解说的什么 0 的归属问题，为什么是对的？
最大流=最小割：最小割边之后s到t就没有流了，因为不管是狼，还是羊，到源点，汇点的连边，流量均为inf，因此，不可能被割断，那么为什么s到t没有流量了呢，说明狼和羊已经完全被割开了
#include <bits/stdc++.h>#define s 0#define t (m*n+1)#define xuhao(i,j) ((i-1)*m+j)#define hefa(x,di,top) (di<=x&&x<=top)using namespace std;const int maxn=1e4+2,maxm=1e5+1,inf=1e9;int n,m,a,tot=1,head[maxn],dep[maxn],ans;const int d[4][2]={ {0,1},{0,-1},{-1,0},{1,0}};struct edge{ int to,next,w;}e[maxm];void addedge(int x,int y,int w){ e[++tot].to=y;e[tot].w=w;e[tot].next=head[x];head[x]=tot; e[++tot].to=x;e[tot].w=0;e[tot].next=head[y];head[y]=tot;}bool bfs(){ memset(dep,0,sizeof(dep)); queue<int>q; q.push(s);dep[s]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=head[x];i;i=e[i].next) { int y=e[i].to,w=e[i].w; if(w&&!dep[y]) { dep[y]=dep[x]+1; q.push(y); } } } return dep[t];}int dfs(int x,int flow){ if(x==t)return flow; int sum=0; for(int i=head[x];i;i=e[i].next) { int y=e[i].to,w=e[i].w; if(w&&dep[y]==dep[x]+1) { int f=dfs(y,min(flow,w)); e[i].w-=f;e[i^1].w+=f; flow-=f;sum+=f; } } if(!sum)dep[x]=0; return sum;}int main(){ ios::sync_with_stdio(0); scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&a); if(a==1) addedge(s,xuhao(i,j),inf); else if(a==2) addedge(xuhao(i,j),t,inf); for(int k=0;k<=3;k++) { int x=i+d[k][0],y=j+d[k][1]; if(hefa(x,1,n)&&hefa(y,1,m))addedge(xuhao(i,j),xuhao(x,y),1); } } } while(bfs())ans+=dfs(s,inf); printf("%d\n",ans); return 0;}