【bzoj】 1412: [ZJOI2009]狼和羊的故事

Description

“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．” Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。 通过仔细观察，Orez发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。

Input

文件的第一行包含两个整数n和m。接下来n行每行m个整数，1表示该格子属于狼的领地，2表示属于羊的领地，0表示该格子不是任何一只动物的领地。

Output

文件中仅包含一个整数ans，代表篱笆的最短长度。

Sample Input

2 2
2 2
1 1

Sample Output

2

数据范围
10%的数据 n，m≤3
30%的数据 n，m≤20
100%的数据 n，m≤100

 

明显最小割 

挖掘栅栏的本质：只能建在相邻两个，且建好后使得狼和羊之间不存在通路。而割的定义是：使S集和T集不存在通路。而题目又要求建的栅栏最少，于是就是最小割问题了。

 

主要是建边 从源点连向狼的无穷边

从羊向汇点的无穷边 

再是狼到空地和羊

 

空地到空地和羊

 

#include<queue>
#include<cstdio>
#include<iostream>
#define MAXN 100010

const int INF=0x7fffffff;

using namespace std;

int map[101][101];

int n,m,st,en,ans; 

int x[4]={0,1,0,-1};
int y[4]={1,0,-1,0};

struct node {
    int to;
    int next;
    int val;
};
node e[MAXN];

int head[MAXN],tot=1;

int depth[MAXN],cur[MAXN];

queue<int> q;

inline void read(int&x) {
    int f=1;x=0;char c=getchar();
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-48;c=getchar();}
    x=x*f;
}

inline void add(int x,int y,int val) {
    e[++tot].to=y;
    e[tot].val=val;
    e[tot].next=head[x];
    head[x]=tot;
}

inline int bfs() {
    for(int i=0;i<=en;i++) cur[i]=head[i],depth[i]=-1;
    while(!q.empty()) q.pop();
    q.push(st);depth[st]=0;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=0;i=e[i].next) {
            int to=e[i].to;
            if(e[i].val>0&&depth[to]==-1) {
                depth[to]=depth[u]+1;
                q.push(to);
                if(to==en) return true;
            } 
        }
    }
    return false;
}

inline int dinic(int now,int flow) {
    if(now==en) return flow;
    int rest=0,delat;
    for(int & i=cur[now];i!=0;i=e[i].next) {
        int to=e[i].to;
        if(depth[to]==depth[now]+1&&e[i].val>0) {
            delat=dinic(to,min(e[i].val,flow-rest));
            if(delat) {
                e[i].val-=delat;
                e[i^1].val+=delat;
                rest+=delat;
                if(rest==flow) break;
            }
        }
    }
    if(flow!=rest) depth[now]=-1;
    return rest;
}

int main() {
    read(n);read(m);
    en=n*m+1;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++) {
          read(map[i][j]);
          if(map[i][j]==1) add(st,(i-1)*m+j,INF),add((i-1)*m+j,st,0);
          else if(map[i][j]==2) add((i-1)*m+j,en,INF),add(en,(i-1)*m+j,0);
      }
    for(int i=1;i<=n;i++) 
      for(int j=1;j<=m;j++) 
        for(int k=0;k<4;k++) {
            int xx=i+x[k];
            int yy=j+y[k];
            if(xx<1||yy<1||xx>n||yy>m||map[i][j]==2) continue;
            if(map[xx][yy]!=1) add((i-1)*m+j,(xx-1)*m+yy,1),add((xx-1)*m+yy,(i-1)*m+j,0);
        } 
    while(bfs()) ans+=dinic(st,INF);
    printf("%d
",ans);
    return 0;
}