BZOJ 2132：圈地計劃（最小割 / 二維網格）

一、題目大意

N×M 網格，每格選商業區（收益 Aij）或工業區（收益 Bij）。相鄰格子類型不同，每對產生額外收益 Cij。求最大總收益。N,M ≤ 100。

二、解題思路：最小割模型

將格子黑白染色（棋盤染色）。
- 黑格：s→i 容量 Aij，i→t 容量 Bij
- 白格：s→i 容量 Bij，i→t 容量 Aij
- 相鄰格子 i,j：雙向邊 i→j、j→i 容量 Cij + Cji (實際為 C[i][j]+C[i][j]? 原題為 Cij 為矩陣，相鄰收益為 k*Cij，建模為雙向容量 C[i][j]+C[ni][nj])
總收益 = 所有 Aij+Bij + 所有相鄰 Cij+Cji - 最小割。
原理：割斷 s→i 表示選另一類型，割斷相鄰邊表示類型不同產生收益。

三、代碼實現（C++，Dinic）

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 10100;
const int MAXM = 100100;
const int INF = 1e9;

struct Edge { int to, next, cap; } e[MAXM];
int head[MAXN], cur[MAXN], dis[MAXN], C[105][105];
int n, m, s, t, tot=1, ans=0, sum=0;

void addEdge(int u, int v, int c1, int c2) {
    e[++tot] = {v, head[u], c1}; head[u] = tot;
    e[++tot] = {u, head[v], c2}; head[v] = tot;
}

bool bfs() {
    memset(dis, -1, sizeof(dis));
    queue q; q.push(s); dis[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].to;
            if(e[i].cap && dis[v]==-1){
                dis[v]=dis[u]+1; q.push(v);
            }
        }
    }
    return dis[t]!=-1;
}

int dfs(int u, int f) {
    if(u==t) return f;
    int flow=0;
    for(int &i=cur[u];i;i=e[i].next){
        int v=e[i].to;
        if(e[i].cap && dis[v]==dis[u]+1){
            int pushed=dfs(v, min(f-flow, e[i].cap));
            e[i].cap-=pushed; e[i^1].cap+=pushed;
            flow+=pushed;
            if(flow==f) return flow;
        }
    }
    if(!flow) dis[u]=-1;
    return flow;
}

void dinic() {
    while(bfs()){
        memcpy(cur, head, sizeof(head));
        ans+=dfs(s, INF);
    }
}

int id(int x, int y) { return (x-1)*m + y; }

int main() {
    scanf("%d%d", &n, &m);
    s = n*m+1; t = s+1;
    // 讀 A
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){
        int x; scanf("%d",&x); sum+=x;
        if((i+j)&1) addEdge(s, id(i,j), x, 0);
        else addEdge(id(i,j), t, x, 0);
    }
    // 讀 B
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){
        int x; scanf("%d",&x); sum+=x;
        if((i+j)&1) addEdge(id(i,j), t, x, 0);
        else addEdge(s, id(i,j), x, 0);
    }
    // 讀 C
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&C[i][j]);
    // 相鄰邊
    for(int i=1;i<=n;++i) for(int j=1;j