# Description
Luogu传送门
# Solution
- 最大费用最大流
虽然叫方格取数加强版，但是感觉跟方格取数没半毛钱关系（
我们还是要从当前点向下，向右连边。
-
观察题意，一个点被走过之后权值变为 0，但是还可以继续走，所以我们可以把一个点拆成入点和出点，然后从入点向出点连两条边。
-
建一条流量为 1，费用为 的边。
-
再建一条流量为 ，费用为 0 的边。
表示第一次走可以获得 的收益，但只能走一次，后面再走到当前点时没有收益。
-
-
从当前点向下方和右方连一条流量为 ，费用为 0 的边，仅表示一种联通关系。
超级源点和超级汇点可建可不建，直接用 的入点当源点， 的出点当汇点即可。
# 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
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 = 5e3 + 10;
const int M = 2e5 + 10;
const int INF = 2e9;
int n, k, ans, s, t;
struct node{
int v, w, cost, nxt;
}edge[M];
int head[N], tot = 1;
inline void add(int x, int y, int z, int cost){
edge[++tot] = (node){y, z, cost, head[x]};
head[x] = tot;
}
inline void Add(int x, int y, int z, int cost){
add(x, y, z, cost), add(y, x, 0, -cost);
}
int dis[N], f[N], p[N];
bool vis[N];
inline bool spfa(){
queue <int> q;
memset(vis, 0, sizeof(vis));
memset(dis, 128, sizeof(dis));
q.push(s), vis[s] = 1, dis[s] = 0, f[s] = INF;
while(!q.empty()){
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = head[x]; i; i = edge[i].nxt){
if(!edge[i].w) continue;
int y = edge[i].v;
if(dis[y] < dis[x] + edge[i].cost){
dis[y] = dis[x] + edge[i].cost;
f[y] = min(f[x], edge[i].w), p[y] = i;
if(!vis[y]) vis[y] = 1, q.push(y);
}
}
}
return dis[t] > -INF;
}
inline void solve(){
while(spfa()){
int x = t;
while(x != s){
int i = p[x];
edge[i].w -= f[t], edge[i ^ 1].w += f[t];
x = edge[i ^ 1].v;
}
ans += dis[t] * f[t];
}
}
int main(){
n = read(), k = read();
s = 1, t = P(n, n, 1);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j){
int w = read();
Add(P(i, j, 0), P(i, j, 1), 1, w);
Add(P(i, j, 0), P(i, j, 1), k - 1, 0);
if(i < n) Add(P(i, j, 1), P(i + 1, j, 0), k, 0);
if(j < n) Add(P(i, j, 1), P(i, j + 1, 0), k, 0);
}
solve();
write(ans), puts("");
return 0;
}
