题目传送门(BZOJ)
>原文链接<

题解 :

看上去就是一道最小割, 做起来也是一道最小割

我们只需要考虑如何把羊和狼隔开就行了不是吗

对于羊的领地, 从$S$到其连一条$val = INF$的边, 因为它不能被割掉

同理, 从狼的领地向$T$连一条$val = INF$的边.

对于建篱笆, 我们从每个点向四周连一条权值为$1$的边, 代表可以通过,

而求一个最小割, 就可以通过割掉权值为$1$的边实现隔开狼和羊

大功告成! 我甚至懒得再写一次Dinic.

代码 :

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <queue>using namespace std;const int N =1e5+10;const int inf = 0x3f3f3f3f;#define P(i,j) ((i-1)*m+j)int head[N+10], to[N*6+10], val[N*6+10], nxt[N*6+10];int cnt = 1;int dep[N+10];int n, m, s, t;void add_edge(int a,int b,int c) { to[++cnt] = b; nxt[cnt] = head[a]; head[a] = cnt; val[cnt] = c; to[++cnt] = a; nxt[cnt] = head[b]; head[b] = cnt; val[cnt] = 0;}queue<int>q;bool bfs() { memset(dep,0,sizeof(dep)); while(!q.empty())q.pop(); q.push(s); dep[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=nxt[i]) { if(!dep[to[i]]&&val[i]) { dep[to[i]]=dep[u]+1; q.push(to[i]); } } } return dep[t]!=0;}int dfs(int p,int mf) { int nf=0; if(p==t)return mf; for(int i=head[p];i;i=nxt[i]) { if(dep[to[i]]==dep[p]+1&&val[i]) { int tmp=dfs(to[i],min(mf-nf,val[i])); if(!tmp)dep[to[i]]=0; nf+=tmp; val[i]-=tmp; val[i^1]+=tmp; if(nf==mf)break; } } return nf;}void dinic() { int ans=0; while(bfs()) { ans+=dfs(s,inf); } printf("%d\n",ans);}int main() { scanf("%d%d",&n,&m); s = n*m+1, t = n*m+2; for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) { int x; scanf("%d",&x); if(x==1) add_edge(s, P(i,j), inf); else if(x==2) add_edge(P(i,j), t, inf); if(i>1) add_edge(P(i,j),P(i-1,j),1); if(i<n) add_edge(P(i,j),P(i+1,j),1); if(j>1) add_edge(P(i,j),P(i,j-1),1); if(j<m) add_edge(P(i,j),P(i,j+1),1); } dinic();}