「网络流 24 题」方格取数
题解：对每个点进行染色，将第一个染为黑色，然后相邻的为白色，这样交替染色然后将整个方格分成黑白两种不同的颜色，从源点向每个白色的方块连容量为权值的边，从黑色向汇点连接容量为权值的边，从白色的向相邻的黑色的点连容量为无穷大的边，跑最大点权独立集

#include <bits/stdc++.h> 

const int MAXN = 1000000,INF = 10000000;
const int fx[] = {1,-1,0,0},fy[]={0,0,1,-1};

using namespace std;

int n,m,s,t,e = 2,sum;
int d[MAXN],cur[MAXN],head[MAXN],data[100][100];
bool b[100][100];

struct node{
    int v,c,f,next;
}edge[MAXN];

inline void addedge(int u,int v,int w){
    edge[e] = (node){v,w,0,head[u]};head[u] = e++;
    edge[e] = (node){u,0,0,head[v]};head[v] = e++;
}

inline bool check(int x,int y){
    if(x < 1 || x > m) return false;
    if(y < 1 || y > n) return false;
    return true;
}

inline void init()
{
    scanf("%d%d",&m,&n);
    s = 0;t = m * n + 1;    
    for(int i = 1;i <= m;i++)
        for(int j = 1;j <= n;j++){
            scanf("%d",&data[i][j]);
            sum += data[i][j];
        }
    b[1][1] = 1;
    for(int i = 1;i <= m;i++)
        for(int j = 1;j <= n;j++){
            if(j == 1 && i != 1) b[i][j] = b[i-1][j] ^ 1;
            else b[i][j] = b[i][j-1] ^ 1;
        }
        
    for(int i = 1;i <= m;i++)
        for(int j = 1;j <= n;j++)
            if(b[i][j])    addedge(s,(i-1)*n+j,data[i][j]);
            else addedge((i-1)*n+j,t,data[i][j]);

    for(int i = 1;i <= m;i++)
        for(int j = 1;j <= n;j++)
            for(int k = 0;k <= 3;k++)
                if(check(i+fx[k],j+fy[k])&&b[i][j])
                    addedge((i-1)*n+j,(i+fx[k]-1)*n+j+fy[k],INF);
                        
}

queue<int>Q;
inline bool bfs(){
    memset(d,0,sizeof(d));
    d[s] = 1;Q.push(s);
    while(!Q.empty()){
        int x = Q.front();Q.pop();
        for(int i = head[x];i;i = edge[i].next){
            node E = edge[i];
            if(!d[E.v] && E.c > E.f){
                d[E.v] = d[x] + 1;
                Q.push(E.v);
            }
        }
    }
    return d[t] ? true : false;
} 

int dfs(int x,int a){
    if(x == t || a == 0) return a;
    int flow = 0,f;
    for(int &i = cur[x];i;i = edge[i].next){
        node &E = edge[i];
        if(d[E.v] == d[x] + 1 && (f = dfs(E.v,min(E.c - E.f,a))) > 0){
            E.f += f;
            edge[i^1].f -= f;
            flow += f;
            a -= f;
            if(a == 0) break;
        }
    }
    return flow;
} 

inline int max_flow(){
    int flow = 0;
    while(bfs()){
        for(int i = s;i <= t;i++) cur[i] = head[i];
        flow += dfs(s,INF);
    }
    return flow;
}

int main()
{
    init();
    sum -= max_flow();
    printf("%d\n",sum);
    return 0;
}