[文章目录]
Description
Orez的羊狼圈可以看作一个n * m个矩阵格子，这个矩阵的边缘已经装上了篱笆。Orez决定在羊狼圈中再加入一些篱笆，要将羊狼分开来养。 通过仔细观察，Orez发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。n,m<=100
网络流最小割。
s向狼连边，t向羊连边，流量为inf。对于相邻格子互相连边，流量为1。此图的最小割即为答案。
但是写的时候想到了一个问题：对于一个篱笆被修建后等价于割断正反两条路。于是就对于正反两方向都新建一条边限流，具体为什么不加限流也对，我也不是很清楚，感性理解好像没啥毛病。。。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,s,t,ans;
int head[51000],to[250000],nxt[250000],f[250000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
queue<int>q;
int dis[51000];
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
dis[s]=0; q.push(s); int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d",&n,&m);
int tot=n*m,I=n*m; s=I*5+1; t=s+1;
for(int i=1;i<=n;++i)
for(int j=1;j<m;++j)
{
add(tot+i*m-m+j,tot+I+i*m-m+j,1);
add(i*m-m+j,tot+i*m-m+j,1);
add(i*m-m+j+1,tot+i*m-m+j,1);
add(tot+I+i*m-m+j,i*m-m+j,1);
add(tot+I+i*m-m+j,i*m-m+j+1,1);
}
tot+=(I<<1);
for(int i=1;i<n;++i)
for(int j=1;j<=m;++j)
{
add(tot+i*m-m+j,tot+I+i*m-m+j,1);
add(i*m-m+j,tot+i*m-m+j,1);
add(i*m+j,tot+i*m-m+j,1);
add(tot+I+i*m-m+j,i*m-m+j,1);
add(tot+I+i*m-m+j,i*m+j,1);
}
int x;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
scanf("%d",&x);
if(x==1) add(s,i*m-m+j,inf);
if(x==2) add(i*m-m+j,t,inf);
}
while(bfs()) ans+=dinic(s,inf);
printf("%d\n",ans);
return 0;
}