题解 | #[ZJOI2009]狼和羊的故事#

该问题是一个最小割问题：如何放最少的篱笆使得羊狼领域分开。

建图：我们将相邻的土地都连上权值为1的无向边。再将额外增加一个源点和一个汇点，将所有狼的领地和源点相连、羊的领地和汇点相连，边权为一个大数即可。

建完图后跑一遍dinic就可以了。

注意：加边加的是无向边不要重复加边。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100100;
const int maxm = maxn << 2;
const LL inf = 0x7f7f7f7f7f7f7f7f;
const int big = 1e7;
int fx[] = {0, 1};
int fy[] = {1, 0};
typedef struct Dinic {
    typedef struct Edge {
        int u, v, next;
        LL w;
    }Edge;
    int head[maxn], hcnt;
    int cur[maxn];
    LL dep[maxn];
    Edge e[maxm];
    int S, T, N;
    
    void init() {
        memset(head, -1, sizeof head);
        hcnt = 0;
        S = T = N = 0;
    }
    
    void adde(int u, int v, LL w) {
        e[hcnt].u = u, e[hcnt].v = v, e[hcnt].w = w;
        e[hcnt].next = head[u]; head[u] = hcnt++;
        e[hcnt].u = v, e[hcnt].v = u, e[hcnt].w = w;
        e[hcnt].next = head[v]; head[v] = hcnt++;
    }
    
    // BFS 分层
    int bfs() {
        for(int i = 0; i <= N; i++) {
            dep[i] = inf;
        }
        queue<int> q;
        q.emplace(S); dep[S] = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int i = head[u]; ~i; i = e[i].next) {
                int v = e[i].v;
                LL w = e[i].w;
                if(w > 0 && dep[u] + 1 < dep[v]) {
                    dep[v] = dep[u] + 1;
                    if(v == T) return 1;
                    q.emplace(v);
                }
            }
        }
        return dep[T] != inf;
    }
    
    // DFS 增广
    LL dfs(int u, LL mw) {
        if(u == T) return mw;
        for(int i = cur[u]; ~i; i = e[i].next) {
            cur[u] = i;
            int v = e[i].v;
            LL w = e[i].w;
            if(w <= 0 || dep[v] != dep[u] + 1) continue;
            LL cw = dfs(v, min(w, mw));
            if(cw <= 0) continue;
            e[i].w -= cw;
            e[i ^ 1].w += cw;
            return cw;
        }
        // 找一条链 S -> T
        // min w
        return 0;
    }
    
    LL dinic() {
        LL ret = 0;
        while(bfs()) {
            for(int i = 0; i <= N; i++) cur[i] = head[i];
            while(LL d = dfs(S, inf)) {
                ret += d;
            }
        }
        return ret;
    }
} Dinic;
int main() {
    int n, m;
    cin >> n >> m;
    Dinic d;
    d.init();
    int s = 1, t = 2;
    d.S = 1; d.T = t; d.N = 11000;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int g, u = i * 100 + j;
            cin >> g;
            if(g == 1) d.adde(s, u, big);
            if(g == 2) d.adde(t, u, big);
            for(int k = 0; k < 2; k++) {
                int x = i + fx[k], y = j + fy[k];
                if(x < 1 || x > n || y < 1 || y > m) continue;
                int v = x * 100 + y;
                d.adde(u, v, 1);
            }
        }
    }
    LL ans = d.dinic();
    cout << ans << '\n';
    return 0;
}