网络流，最大权独立点集

题意：

##分析：
看到这一题，我的第一反应是二分图求最大独立点集。想要用HK算法干掉他。但是仔细一看并非如此，题目让球的是最大权独立点集。这就是完全不同的问题了。

真正的解法推荐看论文：胡伯涛《最小割模型在信息学竞赛中的应用》，直接跳到第五部分读就行了。

不得不感叹，真是巧妙。我们只要建图起点和左半边点连边权值为点权值，做半边点和右半边点连边权值为inf，右半边点和终点连边权值为点权值。再求其最小割，也就是最大流。我们就得到了最小权点覆盖集。然后根据点覆盖集和点独立集的互补性。
我们用总权值-最小点权覆盖集的权值就得到了最大点权独立集的权值。

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int max_n = 55;
const int max_m = 55;
const int inf = 2e9;
int n, m;
int start = 2501, ed = 2502;

struct edge
{
    int to, cap, rev, next;
}E[max_n * max_m * 16];
int head[max_n * max_m];
int cnt = 1;
void add(int from, int to, int cap) {
    E[cnt].to = to;
    E[cnt].cap = cap;
    E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];
    head[from] = cnt++;
    E[cnt].to = from;
    E[cnt].cap = 0;
    E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];
    head[to] = cnt++;
}
void init() {
    fill(head, head + max_n * max_m, false);
    cnt = 1;
}


int dist[max_n * max_m];
int iter[max_n * max_m];
bool searchpath(int s, int t) {
    fill(dist, dist + max_n * max_m, -1);
    dist[s] = 0;queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();que.pop();
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (dist[e.to] != -1 || e.cap == 0)continue;
            dist[e.to] = dist[u] + 1;
            que.push(e.to);
        }
    }return dist[t] != -1;
}
int matchpath(int u,int t,int f) {
    if (u == t)return f;
    for (int& i = iter[u];i;i = E[i].next) {
        edge& e = E[i];
        if (dist[e.to] <= dist[u] || e.cap == 0)continue;
        int d = matchpath(e.to, t, min(f, e.cap));
        if (d <= 0)continue;
        e.cap -= d;
        E[e.rev].cap += d;
        return d;
    }return false;
}
int dinic(int s,int t) {
    int flow = 0;int f;
    while (searchpath(s, t)) {
        for (int i = 1;i <= ed;i++)iter[i] = head[i];
        while (f = matchpath(s, t, inf))
            flow += f;
    }return flow;
}

int main() {
    ios::sync_with_stdio(0);
    while (cin >> m >> n) {
        int cap;int sum = 0;init();
        for (int i = 0;i < m;i++) {
            for (int j = 1;j <= n;j++) {
                cin >> cap;sum += cap;
                if ((i + j) & 1) {
                    add(start, i * n + j, cap);
                    if (i != 0)add(i * n + j, i * n - n + j, inf);
                    if (i != m - 1)add(i * n + j, i * n + n + j, inf);
                    if (j != 1)add(i * n + j, i * n + j - 1, inf);
                    if (j != n)add(i * n + j, i * n + j + 1, inf);
                }
                else add(i * n + j, ed, cap);
            }
        }cout << sum - dinic(start, ed) << endl;
    }
}