[BZOJ 1324] Exca王者之剑 最大流

传送门·Teleport!

题目大意

解题报告

2018/4/12 Update: 发现以前的题解不负责任地出错了..已修正。

此题bzoj的Discuss上有很多好的测试数据，我就不给啦！
怎么感觉这题和Ex咖喱棒没任何关系啊。。

首先发现如果取了一个格子那么格子四周的格子都不能取，
因为格子内的数大于0，那么题目就变成了：

求N*M矩阵内取格子内的数字，使得数字和最大且格子两两不相邻。

接下来就是套路了。。
发现把每个格子的(i,j)按照i+j的奇偶性分成黑白两类，(就是按照网格状二染色)，那么黑色选了，相邻的白色就不能选。
这是一个二分图, 所以可以做到用二染色和连接INF边满足相邻两个节点不能同时被选择的约束。
那么把黑色点和S(源点)连边，权值为格子上的数字。把白色点和T(汇点点)连边，权值也为格子上的数字，每个白点向相邻的黑点连INF的边。
现在考虑最小割把所有点分为两部分。
对于白点, s集(源点所在集合)中的点代表不被选中,t集(汇点所在集和)中的点被选中, 对于黑点则恰好相反。
答案就等于总权值和减去最小割啦~
下面上代码：

代码

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>

const int INF = 0x3f3f3f3f;
const int MAXN = 100+10;

using std :: min;
using std :: max;

namespace isap {
    const int MAXD = 10000;
    const int MAXE = 1000000;

    struct Node {
        int v, w, bk, nxt;
    } d[MAXE];
    int head[MAXD], etot;
    inline int addEdge (int a, int b, int c) {
        etot ++;
        d[etot].v = b;
        d[etot].w = c;
        d[etot].bk = etot + 1;
        d[etot].nxt = head[a];
        head[a] = etot;
        etot ++;
        d[etot].v = a;
        d[etot].w = 0;
        d[etot].bk = etot - 1;
        d[etot].nxt = head[b];
        head[b] = etot;
        //printf("%d -> %d: %d\n", a, b, c);
        return etot;
    }

    int dis[MAXD], vd[MAXD];
    int seq[MAXD+100];
    void bfs (int s) {
        int lef, rig;
        memset(dis, 0x3f, sizeof dis);
        dis[seq[lef = rig = 0] = s] = 0;
        while(lef <= rig) {
            int u = seq[lef++];
            for(int e = head[u]; e; e = d[e].nxt)
                if(dis[d[e].v] > dis[u] + 1) {
                    dis[d[e].v] = dis[u] + 1;
                    seq[++rig] = d[e].v;
                }
        }
    }
    int S, T, N;
    int dfs (int u, int val) {
        //printf("at:%d, val:%d\n", u, val);
        if(u == T) return val;
        int rest = val;
        for(int e = head[u]; e; e = d[e].nxt)
            if(d[e].w && dis[d[e].v]+1 == dis[u]) {
                int t = dfs(d[e].v, min(rest, d[e].w));
                rest -= t;
                d[e].w -= t;
                d[d[e].bk].w += t;
                if(!rest) return val;
                if(dis[S] >= N) return val - rest;
            }
        if(val == rest) {
            if(!(--vd[dis[u]])) {dis[S] = N; return 0;}
            dis[u] = N;
            for(int e = head[u]; e; e = d[e].nxt)
                if(d[e].w) dis[u] = min(dis[u], dis[d[e].v] + 1);
            ++ vd[dis[u]];
            return 0;
        }
        return val - rest;
    }

    int sap (int s, int t, int n) {
        S = s, T = t, N = n;
        bfs(T);
        for(int i = 1; i<=N; i++)
            if(dis[i] <= N) vd[dis[i]] ++;
        int flow = 0;
        while(dis[S] < N) flow += dfs(S, INF);
        return flow;
    }
    void clear() {
        etot = 0;
        memset(head, 0, sizeof head);
    }
}
int N, M;
int val[MAXN][MAXN];
int getVid (int x, int y) {
    return (x-1)*M+y;
}
int main () {
    int sum = 0;
    scanf("%d%d", &N, &M);
    int S = 1, T = S+N*M+1;
    for(int i = 1; i<=N; i++)
        for(int j = 1; j<=M; j++) {
            scanf("%d", &val[i][j]), sum += val[i][j];
            if((i+j)&1) isap :: addEdge(S, S+getVid(i, j), val[i][j]);
            else isap :: addEdge(S+getVid(i, j), T, val[i][j]);
        }
    for(int i = 1; i<=N; i++)
        for(int j = 1; j<=M; j++)
            if((i+j)&1) {
                int id = getVid(i, j);
                if(i != 1) isap :: addEdge(S+id, S+getVid(i-1, j), INF);
                if(i != N) isap :: addEdge(S+id, S+getVid(i+1, j), INF);
                if(j != 1) isap :: addEdge(S+id, S+getVid(i, j-1), INF);
                if(j != M) isap :: addEdge(S+id, S+getVid(i, j+1), INF);
            }
    printf("%d\n", sum - isap :: sap(S, T, T));
}