【题意】：k取方格数。
【题解】：最大费用流。构图：对于每个格子i，拆点 i 和 i'，每对拆点连两条边，一条费用为方格的数值，容量为1，另一条费用为0，容量为inf；对于格子i可以转移到格子j，连边i'->j，费用为0，容量为inf。最后以（1,1）格子为源点，（n,n）为汇点，限定最多增广k次，求最大费用流即为答案。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "queue"
5 using namespace std;
6 const int inf = 1 << 30;
7 #define maxn 5005
8 #define maxm 500000
9 int n, k, s, t;
10 int maz[55][55];
11 int eh[maxn], low[maxn], ans, anscost, tot, dist[maxn], pre[maxn];
12 bool visit[maxn];
13
14 struct Edge {
15 int u, v, cost, cap, flow, next;
16 }et[maxm];
17
18 void init() {
19 tot = 0;
20 memset(eh, -1, sizeof(eh));
21 }
22
23 void add(int u, int v, int cost, int cap, int flow) {
24 Edge e = {u, v, cost, cap, flow, eh[u]};
25 et[tot] = e;
26 eh[u] = tot++;
27 }
28
29 void addedge(int u, int v, int cost, int cap) {
30 add(u, v, cost, cap, 0), add(v, u, -cost, 0, 0);
31 }
32
33 bool spfa() {
34 queue<int> que;
35 fill(&dist[0], &dist[maxn], -inf);
36 memset(visit, false, sizeof(visit));
37 memset(low, 0, sizeof(low));
38 memset(pre, -1, sizeof(pre));
39 visit[s] = true, low[s] = inf, dist[s] = 0;
40 que.push(s);
41 while(!que.empty()) {
42 int u = que.front();
43 que.pop();
44 visit[u] = false;
45 for(int i = eh[u]; i != -1; i = et[i].next) {
46 int v = et[i].v, cost = et[i].cost, cap = et[i].cap, flow = et[i].flow;
47 if(cap - flow && dist[u] + cost > dist[v]) {
48 dist[v] = dist[u] + cost;
49 pre[v] = i;
50 low[v] = min(low[u], cap - flow);
51 if(!visit[v]) {
52 que.push(v);
53 visit[v] = true;
54 }
55 }
56 }
57 }
58 return dist[t] != -inf;
59 }
60
61 void costflow() {
62 ans = anscost = 0;
63 while(ans < k && spfa()) {
64 int x = pre[t];
65 ans += low[t];
66 anscost += low[t] * dist[t];
67 while(x != -1) {
68 et[x].flow += low[t];
69 et[x^1].flow -= low[t];
70 x = pre[et[x].u];
71 }
72 }
73 }
74
75 int pos(int i, int j) {
76 return (i - 1) * n + j;
77 }
78
79 void build() {
80 for(int i = 1; i <= n; i++) {
81 for(int j = 1; j <= n; j++) {
82 int u = pos(i, j);
83 if(j + 1 <= n) addedge(n * n + u, pos(i, j + 1), 0, inf);
84 if(i + 1 <= n) addedge(n * n + u, pos(i + 1, j), 0, inf);
85 }
86 }
87 addedge(2 * n * n, t, 0, inf);
88 }
89
90 int main() {
91 scanf("%d%d", &n, &k);
92 init();
93 for(int i = 1; i <= n; i++)
94 for(int j = 1; j <= n; j++) {
95 scanf("%d", &maz[i][j]);
96 int u = pos(i, j);
97 addedge(u, n * n + u, maz[i][j], 1);
98 addedge(u, n * n + u, 0, inf);
99 }
100 s = 1, t = 2 * n * n + 1;
101 build();
102 costflow();
103 printf("%d\n", anscost);
104 return 0;
105 }
106