#最大流#洛谷 2598 jzoj高中 1632 狼和羊的故事

题目

在一个边缘全是篱笆里的n*m矩阵，有若干只羊和若干只狼，问最少装多少篱笆才能让狼和羊不连通（对于任意的$a_{i,j}$，可与$a_{i-1,j}$，$a_{i+1,j}$，$a_{i,j-1}$，$a_{i,j+1}$之间建篱笆）

分析

题目明显地说明了求最小割（狼和羊不连通），所以就想到了用源点连狼且汇点连羊，流量是$10^6$（很大就对了），当然还有篱笆（四个方向，流量为1），如图所示后，代码不言而喻

代码

#include <cstdio>
#include <cctype>
#include <queue>
#define num(i,j) (i-1)*m+j
#define min(a,b) (a<b)?a:b
using namespace std;
struct node{int y,w,next;}e[100005];
int n,m,s,t,k=1,ans,dis[10005],ls[10005];
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
void add(int x,int y,int w){e[++k].y=y; e[k].w=w; e[k].next=ls[x]; ls[x]=k;e[++k].y=x; e[k].w=0; e[k].next=ls[y]; ls[y]=k;
}
bool bfs(int s){for (int i=1;i<=t;i++) dis[i]=0;queue<int>q; q.push(s); dis[s]=1;while (q.size()){int x=q.front(); q.pop();for (int i=ls[x];i;i=e[i].next)if (e[i].w>0&&!dis[e[i].y]){dis[e[i].y]=dis[x]+1;if (e[i].y==t) return 1;q.push(e[i].y);}}return 0;
}
int dfs(int x,int now){if (x==t||!now) return now;int rest=0,f;for (int i=ls[x];i;i=e[i].next)if (e[i].w>0&&dis[e[i].y]==dis[x]+1){rest+=(f=dfs(e[i].y,min(now-rest,e[i].w)));e[i].w-=f; e[i^1].w+=f;if (now==rest) return rest;}if (!rest) dis[x]=0;return rest;
}
int main(){n=in(); m=in(); s=n*m+1; t=n*m+2;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){int x=in();if (i>1) add(num(i,j),num(i-1,j),1);//四个方向if (i<n) add(num(i,j),num(i+1,j),1);if (j>1) add(num(i,j),num(i,j-1),1);if (j<m) add(num(i,j),num(i,j+1),1);if (!x) continue;if (x==1) add(s,num(i,j),1e6);else add(num(i,j),t,1e6);}while (bfs(s)) ans+=dfs(s,1e7);return !printf("%d",ans);
}