首页 题解

# Description

观察题意，一个点被走过之后权值变为 0，但是还可以继续走，所以我们可以把一个点拆成入点和出点，然后从入点向出点连两条边。

# Solution

  • 网络流

题意即为选取一个点之后，当前点上下左右均不能选择，求选取的点的最大权值和。

所以我们把矩阵黑白染色，每个黑点向周围的 4 个白点连边，流量为正无穷。

然后建超级源点，超级汇点。源点向黑点连边，流量为黑点的权值；白点向汇点连边，流量为白点的权值。

然后我们对于这张图跑一个最小割，图中剩下的边权和就是能选取的最大和。

所以答案就是 sumsum 减去最小割。最小割 = 最大流 相信大家都知道。

# Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
#define P(i, j) ((i - 1) * m + j)

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2010;
const int INF = 2e9;
int n, m, sum, ans, s, t;
struct node{
    int v, w, nxt;
}edge[N << 1];
int head[N], tot = 1;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

inline void add(int x, int y, int z){
    edge[++tot] = (node){y, z, head[x]};
    head[x] = tot;
}

int dep[N];

inline bool bfs(){
    queue <int> q;
    memset(dep, 0, sizeof(dep));
    q.push(s), dep[s] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = head[x]; i; i = edge[i].nxt){
            int y = edge[i].v;
            if(edge[i].w && !dep[y])
                dep[y] = dep[x] + 1, q.push(y);
        }
    }
    return dep[t];
}

inline int dfs(int x, int lim){
    if(x == t || !lim) return lim;
    int flow = 0;
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(edge[i].w && dep[y] == dep[x] + 1){
            int res = dfs(y, min(lim, edge[i].w));
            lim -= res, flow += res, edge[i].w -= res, edge[i ^ 1].w += res;
        }
    }
    if(!flow) dep[x] = 0;
    return flow;
}

inline void dinic(){
    while(bfs()) ans += dfs(s, INF);
}

inline bool check(int x, int y){
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

int main(){
    n = read(), m = read();
    t = P(n, m) + 1;
    for(int i = 1, z; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            sum += (z = read());
            if(!((i + j) & 1)){
                add(s, P(i, j), z), add(P(i, j), s, 0);
                for(int k = 0; k < 4; ++k){
                    int x = i + dx[k], y = j + dy[k];
                    if(check(x, y)) add(P(i, j), P(x, y), INF), add(P(x, y), P(i, j), 0);
                }
            }else add(P(i, j), t, z), add(t, P(i, j), 0);
        }
    dinic();
    write(sum - ans), puts("");
    return 0;
}