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

1 1

Sample Output

数据范围

10%的数据 n，m≤3

30%的数据 n，m≤20

100%的数据 n，m≤100

Solution

引用HZWER大神的题解…

挖掘栅栏的本质：只能建在相邻两个，且建好后使得狼和羊之间不存在通路。而割的定义是：使S集和T集不存在通路。而题目又要求建的栅栏最少，于是就是最小割问题了。
从源点向所有狼连一条∞的边，从所有羊向汇点连一条∞的边，这样就能保证狼和羊都在不同的点集里。然后再从狼到相邻的羊和空地，空地到相邻的空地和羊和狼连一条流量为1的边，最大流求最小割即可。
或者将所有点向四周连边。。就是时间长了点

这题有个地方不大理解，后来理解了，就是为什么我们要在两个”0”之间连边，原因如下：

假设我们输入

5 5

2 0 2 0 1

0 2 0 0 1

2 0 2 0 1

0 0 0 0 1

1 1 1 1 1

如果我们不连边，会出现： WrongCut

（灰色点为S点集，大点为源点，汇点未画出。）

这样子，蓝色的边因为我们没有建边，所以最小割割过去代价为0。这样是不对的，因为即使在两个空地之间建栏杆也需要代价，因此我们要在两个空地之间建边。

然后建好图之后就是酱紫啦： CorrectCut

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/**************************************************************
    Problem: 1412
    User: MagHSK
    Language: C++
    Result: Accepted
    Time:100 ms
    Memory:3316 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
using namespace std;
const int INF = 1<<30;
typedef long long LL;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int n, m, id[105][105];
const int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
 
const int maxedge = 100005;
const int maxnode = 50005;
struct MaxFlowSolver {
    int S, T;
    struct edge_type {
        int to, next, r;
    } edge[maxedge];
    int h[maxnode], cur[maxnode], dis[maxnode], cnte, L, R;
    void init() {
        cnte = 1;
        for (int i = 0; i < maxnode; ++i) h[i] = 0;
        S = T = 0;
        L = maxnode;
        R = 0;
    }
    void range(int l, int r) { L = l; R = r; }
    void ins(int u, int v, int w) {
        edge[++cnte].to = v;
        edge[cnte].next = h[u];
        edge[cnte].r = w;
        h[u] = cnte;
        edge[++cnte].to = u;
        edge[cnte].next = h[v];
        edge[cnte].r = 0;
        h[v] = cnte;
    }
    int q[maxnode];
    bool BFS() {
        int head = 0, tail = 1;
        q[0] = S;
        for (int i = L; i <= R; ++i) dis[i] = -1;
        dis[S] = 0;
        int now;
        while (head < tail) {
            now = q[head++];
            for (int i = h[now]; i; i = edge[i].next) {
                if (dis[edge[i].to] == -1 && edge[i].r) {
                    dis[edge[i].to] = dis[now] + 1;
                    q[tail++] = edge[i].to;
                }
            }
        }
        return dis[T] != -1;
    }
    int DFS(int now, int a) {
        if (now == T || a == 0) return a;
        int f, ret = 0;
        for (int &i = cur[now]; i; i = edge[i].next) {
            if (dis[edge[i].to] != dis[now] + 1) continue;
            if (f = DFS(edge[i].to, min(a, edge[i].r))) {
                a -= f;
                ret += f;
                edge[i].r -= f;
                edge[i^1].r += f;
                if (!a) break;
            }
        }
        if (!ret) dis[now] = -1;
        return ret;
    }
    int Dinic(int start, int end) {
        S = start; T = end;
        int ret = 0;
        while (BFS()) {
            for (int i = L; i <= R; ++i) cur[i] = h[i];
            ret += DFS(S, INF);
        }
        return ret;
    }
} G;
 
int land[105][105];
int main() {
    G.init();
    n = getint(); m = getint();
    int sum = 0;
    int S = 1, T = 2;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            id[i][j] = T++;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            land[i][j] = getint();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (land[i][j] == 1) G.ins(S, id[i][j], INF);
            if (land[i][j] == 2) { G.ins(id[i][j], T, INF); continue; }
            for (int k = 0; k < 4; ++k) {
                int tx = i + dx[k], ty = j + dy[k];
                if (1<=tx&&tx<=n&&1<=ty&&ty<=m)
                    if(land[i][j]!=1||land[tx][ty]!=1)
                        G.ins(id[i][j], id[tx][ty], 1);
            }
        }
    G.range(S, T);
    int ans = G.Dinic(S, T);
    printf("%d", ans);
    return 0;
}