【浙江省省选2009】狼和羊的故事
题目
【ZJOI2009】狼和羊的故事 (Standard IO)
Time Limits: 1000 ms Memory Limits: 256000 KB Detailed Limits
Description
“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．”
Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！
Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。
通过仔细观察，Orez发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。
Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。
Input
输入数据存放在文本文件ws.in中。
文件的第一行包含两个整数n和m。接下来n行每行m个整数，1表示该格子属于狼的领地，2表示属于羊的领地，0表示该格子不是任何一只动物的领地。
Output
输出数据存放在文本文件ws.out中。
文件中仅包含一个整数ans，代表篱笆的最短长度。
Sample Input
2 2
2 2
1 1
Sample Output
2
Data Constraint
Hint
【数据范围】
10%的数据 n，m≤3
30%的数据 n，m≤20
100%的数据 n，m≤100
题解
一眼看，这道题还以为是计算几何。并且直接贪心即可。抱着将信将疑的态度打了一个对拍，发现有一个棘手的“0”。这个“0”会使答案很难计算。我们发现，这个空地要么是属于狼的，要么是属于羊的领地。所以我们可以考虑最小割。基本思路就是，设S为羊的领地，T为狼的领地。如果割得离S近，代表这个"0"属于羊的领地，否则反之，然后跑一遍最小割最大流。
正解
我想不到其他方法了。故只有一种方法。
建一个原点S表示羊的领地；T点表示狼的领地。原先就属于羊的领地就朝S点连一条边权为无限大的边；原先属于狼的领地就朝T点同理。中间不确定的点就落在中间。将相邻的点连起来，边权为1。然后直接跑一遍最小割，就是答案。
你可以试这证明一下……
证明
首先，无限大的边保证了原先属于狼与羊的领地不会发生改变。而且，肯定会割掉中间那些关于篱笆的边；对于不定项的点，如果割去左边的边，那么就肯定是归属于羊了，否则反之。
代码
#include<cstdio>
#include<cstring>
#define N 101
#define M 101
using namespace std;
int total1,S,T,n,m;
int fx[5]={0,0,1,0,-1};
int fy[5]={0,1,0,-1,0};
int h[N*M*6],dis[N*M+2],head[N*M*6],next[N*M*6],edge[N*M*6],v[N*M*6];
int a[N][M];
void insert(int x,int y,int z)
{
total1++;
next[total1]=head[x];
head[x]=total1;
edge[total1]=y;
v[total1]=z;
}
bool bfs()
{
memset(dis,0,sizeof(dis));
int l=1,r=1;
h[1]=S;
dis[S]=1;
while (l<=r)
{
int u=h[l];
for (int i=head[u];i;i=next[i])
{
int y=edge[i];
if (v[i]>0&&dis[y]==0)
{
r++;
h[r]=y;
dis[y]=dis[u]+1;
if (y==T) return true;
}
}
l++;
}
return false;
}
int dinic(int k,int flow)
{
if (k==T) return flow;
int rest=flow;
for (int i=head[k];i;i=next[i])
{
int y=edge[i];
if (v[i]>0&&dis[y]==dis[k]+1)
{
int cost;
if (rest>v[i]) cost=v[i];
else cost=rest;
int get=dinic(y,cost);
if (get==0) dis[y]=0;
rest-=get;
v[i]-=get;
v[i^1]+=get;
if (rest==0) break;
}
}
return flow-rest;
}
int main()
{
scanf("%d%d",&n,&m);
total1=1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
S=0;
T=n*m+1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
if (a[i][j]==2)
{
insert(T,(i-1)*m+j,0);
insert((i-1)*m+j,T,999999);
//printf("%d %d %d\n",(i-1)*m+j,T,999999);
}
if (a[i][j]==1)
{
insert((i-1)*m+j,S,0);
insert(S,(i-1)*m+j,999999);
//printf("%d %d %d\n",S,(i-1)*m+j,999999);
}
for (int k=1;k<=4;k++)
{
int xx=i+fx[k];
int yy=j+fy[k];
if (xx>0&&yy>0&&xx<=n&&yy<=m)
{
if (a[i][j]==1)
{
if (a[xx][yy]!=a[i][j])
{
insert((i-1)*m+j,(xx-1)*m+yy,1);
insert((xx-1)*m+yy,(i-1)*m+j,0);
}
}
if (a[i][j]==0)
{
if (a[xx][yy]!=1)
{
insert((i-1)*m+j,(xx-1)*m+yy,1);
insert((xx-1)*m+yy,(i-1)*m+j,0);
}
}
}
}
}
}
//printf("%d\n",(total1-1)/2);
int maxflow=0;
int flow;
while (bfs())
while (flow=dinic(S,999999)) maxflow+=flow;
printf("%d",maxflow);
}