记录编号	562651	评测结果	AAAAAAAAAA
题目名称	K取方格数	最终得分	100
用户昵称	cb	是否通过	通过
代码语言	C++	运行时间	0.246 s
提交时间	2021-07-08 17:39:52	内存使用	1.90 MiB

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;

struct node {
    int next, to, e, co;
} edge[MAXN << 2];

int head[MAXN], cnt = -1;

void add (int from, int to, int e, int co) {
    edge[++ cnt].next = head[from], head[from] = cnt, edge[cnt].to = to, edge[cnt].e = e, edge[cnt].co = co;
    edge[++ cnt].next = head[to], head[to] = cnt, edge[cnt].to = from, edge[cnt].e = 0, edge[cnt].co = -co;
}

int n, k, s, t;

int num (int x, int y, int z) {
    return (x - 1) * n + y + z * n * n;
}

int d[MAXN], incf[MAXN], ins[MAXN], pre[MAXN], ans = 0;

bool spfa () {
    queue <int> p; memset (d, 0xcf, sizeof (d));
    d[s] = 0; ins[s] = 1; incf[s] = 0x3f3f3f3f; p.push (s);
    while (p.size ()) {
        int u = p.front (); p.pop ();
        ins[u] = 0;
        for (int q = head[u]; ~q; q = edge[q].next) {
            int v = edge[q].to;
            if (d[v] < d[u] + edge[q].co && edge[q].e) {
                d[v] = d[u] + edge[q].co;
                pre[v] = q;
                incf[v] = min (incf[u], edge[q].e);
                if (! ins[v]) ins[v] = 1, p.push (v);
            }
        }
    }
    if (d[t] == 0xcfcfcfcf) return false;
    return true;
}

void update () {
    int x = t;
    while (x != s) {
        int i = pre[x];
        edge[i].e -= incf[t];
        edge[i ^ 1].e += incf[t];
        x = edge[i ^ 1].to;
    }
    ans += d[t] * incf[t];
}

int main () {
    memset (head, -1, sizeof (head));
    freopen ("Kgrid.in", "r", stdin);
    freopen ("Kgrid.out", "w", stdout);
    scanf ("%d %d", &n, &k);
    int x;
    s = num (1, 1, 0), t = num (n, n, 1);
    for (int q = 1; q <= n; ++q) {
        for (int w = 1; w <= n; ++w) {
            scanf ("%d", &x);
            add (num (q, w, 0), num (q, w, 1), 1, x);
            add (num (q, w, 0), num (q, w, 1), (k - 1), 0);
            if (q < n) add (num (q, w, 1), num (q + 1, w, 0), k, 0);
            if (w < n) add (num (q, w, 1), num (q, w + 1, 0), k, 0);
        }
    }
    while (spfa ()) update ();
    printf ("%d\n", ans);
    return 0;
}