Description

狼爱上羊啊爱的疯狂, 谁让他们真爱了一场; 狼爱上羊啊并不荒唐, 他们说有爱就有方向......

Orez 听到这首歌, 心想: 狼和羊如此和谐, 为什么不尝试羊狼合养呢? 说干就干! Orez 的羊狼圈可以看作一个 \(n \times 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

Data Range

对于 10% 的数据, 满足 \(n, m \leq 3\)

对于 30% 的数据, 满足 \(n, m \leq 20\)

对于 100% 的数据, 满足 \(n, m \leq 100\)

Explanation

看一眼两边分开就是最小割和最大流......

引用 @hzwer 大神的题解在此:

从源点向所有狼连一条 \(\infty\) 的边, 从所有羊向汇点连一条 \(\infty\) 的边, 这样 就能保证狼和羊都在不同的点集里. 然后再从狼到相邻的羊和空地, 空地到相邻的空地 和羊连一条流量为 \(1\) 的边, 最大流求最小割即可.

查了半天错误终于发现是有一个位置 \(n\) 和 \(m\) 写反了 (233), 对拍了半天都因为 \(n = m\) 搞得不知所措, 还以为是 PE 的另一种表达形式~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxN = 110, maxn = 20010, maxm = 500100;
const lli infinit = 0x003f3f3f3f3f3f3fll;
const int dir_x[4] = { 0,  0,  1, -1 },
          dir_y[4] = { 1, -1,  0,  0 }; // Directions given
#define WOLF_TERRITORY 1
#define HARE_TERRITORY 2
#define NO_MAN_ZONE 0

class Dinic
{
public:
    struct edge
    {
        int u, v; lli flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt, level[maxn];
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v, lli flow)
    {
        // printf("%d %d\n", u, v); // xmPaint compatible (TM).
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        memset(level, 0, sizeof(level));
        queue<int> que;
        que.push(s);
        level[s] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow > 0 && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
            // if (level[t] > 0)
            //     return true;
        }
        if (level[t] > 0)
            return true;
        return false;
    }
    lli find(int p, lli mn)
    {
        if (p == t)
            return mn;
        lli tmp = 0, sum = 0;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (level[ep->v] == level[p] + 1 && ep->flow) {
                tmp = find(ep->v, min(mn - sum, ep->flow));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    lli eval(void)
    {
        lli sum = 0;
        while (make_level())
            sum += find(s, infinit);
        return sum;
    }
} graph;

int n, m;
int arr[maxN][maxN];
#define pos(__x,__y) (m*((__x)-1)+(__y))

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &arr[i][j]);
    // Read data. Building graph.
    // lli large = 10 * n * m; // A very large flow which blocks the way
    lli large = infinit;
    graph.n = n * m + 2;
    graph.s = 0;
    graph.t = 10001;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (arr[i][j] == WOLF_TERRITORY)
                graph.add_edge(graph.s, pos(i,j), large);
            else if (arr[i][j] == HARE_TERRITORY)
                graph.add_edge(pos(i,j), graph.t, large);
            // Checking adjacency.
            for (int k = 0; k < 4; k++) {
                int n_i = i + dir_x[k], n_j = j + dir_y[k];
                if (n_i < 1 || n_i > n || n_j < 1 || n_j > m) continue;
                if (arr[i][j] == HARE_TERRITORY) continue;
                if (arr[i][j] != WOLF_TERRITORY || arr[n_i][n_j] != WOLF_TERRITORY)
                    graph.add_edge(pos(i,j), pos(n_i,n_j), 1);
            }
        }
    // Evaluation on dinic algorithm for result
    lli res = graph.eval();
    printf("%lld\n", res);
    return 0;
}