BJOI2006 狼抓兔子

网络流

BZOJ

题目很显然是要求最小割

根据最大流最小割定理，直接上 Dinic 就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
const int INF = 0x3f3f3f3f;
const int MAXN = 1e3;
int n, m, edge = -1;
int firstEdge[MAXN * MAXN + 5], depth[MAXN * MAXN + 5], curE[MAXN * MAXN + 5], id[MAXN + 5][MAXN + 5];
struct Edge {
    int to, w, nxt;
    Edge(){}
    Edge(int x, int y, int z) {
        to = y;
        w = z;
        nxt = firstEdge[x];
    }
} e[(2 * MAXN * MAXN + 4 * MAXN) * 3 + 5];
inline int read() {
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
inline void addEdge(int x, int y, int z) {
    e[++edge] = Edge(x, y, z);
    firstEdge[x] = edge;
}
bool getDepth() {
    std::queue <int> q;
    memset(depth, 0, sizeof(depth));
    depth[1] = 1;
    q.push(1);
    while(!q.empty()) {
        int from = q.front();
        q.pop();
        for(int k = firstEdge[from]; ~k; k = e[k].nxt) {
            int to = e[k].to, w = e[k].w;
            if(!depth[to] && w > 0) {
                depth[to] = depth[from] + 1;
                q.push(to);
            }
        }
    }
    return depth[n * m] > 0;
}
int Augment(int x, int flow) {
    if(x == n * m) return flow;
    for(int &k = curE[x]; ~k; k = e[k].nxt) {
        int to = e[k].to, w = e[k].w;
        if(depth[to] == depth[x] + 1 && w > 0) {
            int tmp = Augment(to, std::min(flow, w));
            if(tmp > 0) {
                e[k].w -= tmp;
                e[k ^ 1].w += tmp;
                return tmp;
            }
        }
    }
    return 0;
}
int Dinic() {
    int res = 0, tmp = 0;
    while(getDepth()) {
        for(int i = 1; i <= n * m; ++i) curE[i] = firstEdge[i];
        while((tmp = Augment(1, INF)) > 0) res += tmp;
    }
    return res;
}
int main() {
    n = read();
    m = read();
    memset(firstEdge, -1, sizeof(firstEdge));
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) id[i][j] = (i - 1) * m + j;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j < m; ++j) {
            int v = read();
            addEdge(id[i][j], id[i][j + 1], v);
            addEdge(id[i][j + 1], id[i][j], v);
        }
    }
    for(int i = 1; i < n; ++i) {
        for(int j = 1; j <= m; ++j) {
            int v = read();
            addEdge(id[i][j], id[i + 1][j], v);
            addEdge(id[i + 1][j], id[i][j], v);
        }
    }
    for(int i = 1; i < n; ++i) {
        for(int j = 1; j < m; ++j) {
            int v = read();
            addEdge(id[i][j], id[i + 1][j + 1], v);
            addEdge(id[i + 1][j + 1], id[i][j], v);
        }
    }
    printf("%d\n", Dinic());
    return 0;
}