形式化题目

给定 $N \times N$ 的非负整数网格 $a$。选择 $K$ 条从 $(0,0)$ 到 $(N-1,N-1)$ 的单调路径 （每一步只能向右或向下，路径允许重复），记这些路径经过的格子并集为 $S$， 求 $\sum_{(i,j) \in S} a_{i,j}$ 的最大值。同一个格子被多条路径经过时只计一次。

约束：$1 \leqslant N \leqslant 50$，$0 \leqslant K \leqslant 10$，$0 \leqslant a_{i,j} \leqslant 1000$。

题面样例：$N = 3$，$K = 2$。

答案是 $15$：一条路径走 $(0,0)\to(0,1)\to(1,1)\to(2,1)\to(2,2)$，取走 $1+2+2+4+2=11$； 另一条走 $(0,0)\to(0,1)\to(0,2)\to(1,2)\to(2,2)$，只新增 $3+1=4$。 两条路线在 $(0,0),(0,1),(2,2)$ 上重合，但重合的格子不重复计分。

正解

思路

第一步：想一个"看起来很快"的朴素做法。

既然要选 $K$ 条路，最自然的想法是逐条贪心：每次在"还没被取走的权值"上求一条最大权路径， 取走它、把沿途格子清零，重复 $K$ 次。单次最大权路径是标准网格 DP

一次 $O(N^2)$，总共 $O(KN^2)$，对 $N \leqslant 50$ 快得可以忽略。

但它错。 反例（$N=3$，$K=2$）：

最大单条路径是 $(0,0)\to(0,1)\to(1,1)\to(1,2)\to(2,2)$，值 $0+6+3+1+7=17$。 清零之后剩下的格子最多只值 $2$，贪心合计 $19$。 但换一组路线—— $(0,0)\to(1,0)\to(1,1)\to(2,1)\to(2,2)$ 与 $(0,0)\to(0,1)\to(0,2)\to(1,2)\to(2,2)$—— 并集覆盖 $8$ 个格子，合计 $20$。贪心输在"第一条路把中间的好格子独占掉了"。

第二步：定位瓶颈——$K$ 条路径必须联合决策。

贪心的本质是把 $K$ 条路径拆成 $K$ 次互不知情的独立决策。要修正就必须联合决策。有两条路：

1. 把 $K$ 个位置塞进 DP 状态，让 $K$ 条路径并排推进。$K=2$ 的经典方格取数就是这么做的 （四维 DP，两人同时走）。但状态数是 $O(N^{2K})$，$K=10$ 时是天文数字，直接出局。
2. 把"选 $K$ 条路径"当成一个整体结构来优化。 观察题目的计分规则： “第一次经过拿分、之后经过免费”——这不是路径之间互相干扰的复杂耦合， 而是一条容量规则：每个格子的"计分机会"只有 1 次。

第 2 条指向的模型就是网络流：把每个格子的计分机会做成一条容量 1 的弧， 再补一条容量 $K$、费用 $0$ 的旁路弧。于是每条路径走到一个格子时， 会自动"第一次付钱拿分、之后走免费旁路"，$K$ 条路径的联合最优就等价于 $K$ 个单位流的最小费用。

第三步：拆点建图。

每个格子 $(i,j)$ 拆成两个点：入点 $u = 2(iN+j)$ 与出点 $u+1$。

graph LR
    IN["入点 u"] -->|"计分弧 cap=1 cost=-a"| OUT["出点 u+1"]
    IN -.->|"借道弧 cap=K cost=0"| OUT
    OUT -->|"向右 cap=K cost=0"| R["右邻居的入点"]
    OUT -->|"向下 cap=K cost=0"| D["下邻居的入点"]

这张图画的是单个格子的内部结构与它向外的两条移动弧：实线是计分弧（容量 1，费用取负）， 虚线是借道弧（容量 $K$，费用 0），下面两条弧表示只能向右或向下走。 注意计分弧与借道弧是平行的两条弧，共享同一对入点/出点—— 这正是"第一次经过走上面那条、后续经过走下面那条"的实现方式。

完整建图规则：

源点取左上角入点 $0$（所有路径都从这里出发），汇点取右下角出点 $2N^2-1$。 计分弧费用取负，是因为我们要求最小费用流，取反后就等价于最大收益。

为什么这样建模是精确的？ 每个格子的计分弧容量是 1，所以无论有多少条路径经过它， 只有一条能拿到 $a_{i,j}$，其余都必须走费用 0 的借道弧——"只计一次"恰好被容量约束表达了。 反过来，任意一个流量为 $K$ 的整数流都能分解成 $K$ 条 $s \to t$ 路径，而每条路径的走向 （入点 $\to$ 出点 $\to$ 右/下邻居入点）天然就是一条"只右/下"的单调路线。 两个方向的解可以互相转换且目标值一致，所以费用流的最优值就是本题答案。

第四步：负费用弧与势能。

最小费用流每轮要沿费用最小的增广路推流，$K$ 轮即可。本题不能直接跑 Dijkstra： 计分弧的费用 $-a_{i,j}$ 是负的。解决办法是 Johnson 势能重标号： 给每个点一个势 $h[v]$，把弧 $u \to v$ 的费用换成约化费用

只要所有残量弧的约化费用都非负，Dijkstra 就能用，且沿约化最短路增广等价于沿原费用最短路增广。

初始势不能取 $0$（取 $0$ 时计分弧约化费用仍是 $-a_{i,j}$）。 正确做法是令 $h$ 为源点到各点的最短距离：它满足 $h[v] \leqslant h[u] + c(u,v)$， 于是约化费用非负。好消息是这一步在本图里是 $O(V+E)$ 的—— 拆点后点的编号 $0,1,2,\dots,2N^2-1$ 本身就是这张 DAG 的拓扑序 （出点 $u+1$ 只会指向编号更大的入点），按编号从小到大扫一遍残量正向弧做一次松弛即可。

样例的初始势（第一行入点、第二行出点）：

最后一格出点的势是 $-11$，正好是最长单条路径的负权（$1+2+2+4+2$）， 这与"第一条增广路就是最大权路径"一致。此后每轮按 $h[v] \leftarrow h[v] + \mathrm{dist}[v]$ 维护 （$\mathrm{dist}$ 是本次算出的约化距离）， 约化费用保持非负，$K$ 轮都能安心用 Dijkstra。

第五步：边界。

• $K = 0$：一条路线都不安排，答案就是 $0$，直接特判输出。
• $a_{i,j} = 0$：计分弧拿到也没有收益，建图时直接跳过，省一条边。
• 借道弧容量取 $K$ 而不是 $K-1$：多出来的容量永远用不到，却省掉了 $K=1$ 时的边界讨论。

思路与代码的对应。 main.py 只分四层，和上面的推导一一对应： link(u, v, c, w) 负责加一条正向弧与它的反向弧（反向弧编号 e ^ 1）； dag_potential(...) 是上文"初始势 = 源点最短路"那一步，按点编号从小到大扫一遍残量正向弧； min_cost_flow(...) 里 K 轮 Dijkstra + 势能更新 + 沿 prev 回溯推流； max_gain(grid, k) 负责拆点建图，solve() 只做读入、$K=0$ 特判和输出。

代码

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 方格取数：拆点建网络，最小费用最大流（k 次单位流，费用取负）
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;

const ll INF = 1000000000000000000LL;

int size_v;
vector<vector<int> > graph;
vector<int> to;
vector<ll> cap, cost;

// 连一条 u->v 容量 c 费用 w 的弧，紧跟一条残量 0、费用相反的弧
void link(int u, int v, ll c, ll w) {
    graph[u].push_back((int)to.size());
    to.push_back(v);
    cap.push_back(c);
    cost.push_back(w);
    graph[v].push_back((int)to.size());
    to.push_back(u);
    cap.push_back(0);
    cost.push_back(-w);
}

// 源点到各点的最短路当初始势：拆点编号本身就是一个拓扑序
void dag_potential(vector<ll>& h, int s) {
    h.assign(size_v, INF);
    h[s] = 0;
    for (int u = 0; u < size_v; u++) {
        if (h[u] == INF) {
            continue;
        }
        for (int i = 0; i < (int)graph[u].size(); i++) {
            int e = graph[u][i];
            if (cap[e] > 0 && h[u] + cost[e] < h[to[e]]) {
                h[to[e]] = h[u] + cost[e];
            }
        }
    }
}

// 从 s 往 t 送 need 次单位流，返回最小费用
ll min_cost_flow(int s, int t, int need) {
    vector<ll> h;
    dag_potential(h, s);
    ll total = 0;
    for (int it = 0; it < need; it++) {
        vector<ll> dist(size_v, INF);
        vector<int> prev(size_v, -1);
        priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
        dist[s] = 0;
        pq.push(make_pair(0LL, s));
        while (!pq.empty()) {
            pair<ll, int> top = pq.top();
            pq.pop();
            ll d = top.first;
            int u = top.second;
            if (d > dist[u]) {
                continue;
            }
            for (int i = 0; i < (int)graph[u].size(); i++) {
                int e = graph[u][i];
                int v = to[e];
                if (cap[e] > 0) {
                    ll nd = d + cost[e] + h[u] - h[v]; // 约化费用
                    if (nd < dist[v]) {
                        dist[v] = nd;
                        prev[v] = e;
                        pq.push(make_pair(nd, v));
                    }
                }
            }
        }
        if (prev[t] < 0) {
            break; // 送不动了
        }
        for (int v = 0; v < size_v; v++) {
            h[v] += (dist[v] < INF ? dist[v] : 0);
        }
        vector<int> path;
        int v = t;
        while (v != s) {
            path.push_back(prev[v]);
            v = to[prev[v] ^ 1];
        }
        for (int i = 0; i < (int)path.size(); i++) {
            int e = path[i];
            cap[e] -= 1;
            cap[e ^ 1] += 1;
            total += cost[e];
        }
    }
    return total;
}

int main() {
    int n, k;
    if (scanf("%d %d", &n, &k) != 2) {
        return 0;
    }
    vector<vector<ll> > grid(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%lld", &grid[i][j]);
        }
    }
    if (k == 0) {
        printf("0\n");
        return 0;
    }
    size_v = 2 * n * n; // 格子 i 拆成 入点 2i 与 出点 2i+1
    graph.assign(size_v, vector<int>());
    const int STEP[2][2] = {{0, 1}, {1, 0}};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int u = 2 * (i * n + j);
            if (grid[i][j]) { // 第一条穿过它的路径拿走格子里的数
                link(u, u + 1, 1, -grid[i][j]);
            }
            link(u, u + 1, k, 0); // 之后的路径只借道
            for (int s = 0; s < 2; s++) {
                int ni = i + STEP[s][0], nj = j + STEP[s][1];
                if (ni < n && nj < n) {
                    link(u + 1, 2 * (ni * n + nj), k, 0);
                }
            }
        }
    }
    printf("%lld\n", -min_cost_flow(0, size_v - 1, k));
    return 0;
}

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 01:57
# update_at: 2026-10-02 02:05

import sys
from heapq import heappop, heappush

INF = 10**18                    # 最短路里的"不可达"
STEP = ((0, 1), (1, 0))         # 每一步只能往右或往下
TAKE = 1                        # 拿分那条弧的容量：同一个格子只算一次
FREE = 0                        # 借道那条弧的费用：格子被重复经过不再加分


def dag_potential(graph: list[list[int]], to: list[int], cap: list[int],
                  cost: list[int], s: int) -> list[int]:
    """源点到各点的最短路当初始势：拆点编号 0..2N²-1 本身就是 DAG 的拓扑序。"""
    h = [INF] * len(graph)
    h[s] = 0
    for u in range(len(graph)):
        if h[u] == INF:                                         # 尚未连通，跳过
            continue
        for e in graph[u]:
            if cap[e] and h[u] + cost[e] < h[to[e]]:            # 只要还有残量的正向弧
                h[to[e]] = h[u] + cost[e]
    return h


def min_cost_flow(graph: list[list[int]], to: list[int], cap: list[int],
                  cost: list[int], s: int, t: int, need: int) -> int:
    """从 s 往 t 送 need 次单位流，返回最小费用；反向边编号是 e ^ 1。"""
    size = len(graph)
    h = dag_potential(graph, to, cap, cost, s)                  # 有负费用弧，必须先用它定势
    total = 0
    for _ in range(need):
        dist = [INF] * size
        prev = [-1] * size
        dist[s] = 0
        pq = [(0, s)]
        while pq:
            d, u = heappop(pq)
            if d > dist[u]:
                continue
            for e in graph[u]:
                v = to[e]
                if cap[e]:                                      # 只在残量弧上松弛
                    nd = d + cost[e] + h[u] - h[v]              # 约化费用，势成立时非负
                    if nd < dist[v]:
                        dist[v] = nd
                        prev[v] = e
                        heappush(pq, (nd, v))
        if prev[t] < 0:                                         # 送不动了（本题网格总能送满 need 次）
            break
        for v in range(size):
            h[v] += dist[v] if dist[v] < INF else 0
        path: list[int] = []                                    # 这条最短路经过的弧，反向走回去
        v = t
        while v != s:
            path.append(prev[v])
            v = to[prev[v] ^ 1]
        for e in path:
            cap[e] -= 1
            cap[e ^ 1] += 1
        total += sum(cost[e] for e in path)
    return total


def max_gain(grid: list[list[int]], k: int) -> int:
    """k 条从左上到右下的单调路径最多能取走多少整数（同一格只计一次）。"""
    n = len(grid)
    size = 2 * n * n                                            # 格子 i 拆成 入点 2i 与 出点 2i+1
    graph: list[list[int]] = [[] for _ in range(size)]
    to: list[int] = []
    cap: list[int] = []
    cost: list[int] = []

    def link(u: int, v: int, c: int, w: int) -> None:
        """连一条 u->v 容量 c 费用 w 的弧，紧跟一条残量 0、费用相反的弧。"""
        graph[u].append(len(to))
        to.append(v)
        cap.append(c)
        cost.append(w)
        graph[v].append(len(to))
        to.append(u)
        cap.append(0)
        cost.append(-w)

    for i in range(n):
        for j in range(n):
            u = 2 * (i * n + j)
            if grid[i][j]:                                      # 第一条穿过它的路径拿走格子里的数
                link(u, u + 1, TAKE, -grid[i][j])
            link(u, u + 1, k, FREE)                             # 之后的路径只借道，不再加分
            for di, dj in STEP:
                if i + di < n and j + dj < n:
                    link(u + 1, 2 * ((i + di) * n + j + dj), k, FREE)   # 走到右 / 下邻居的入点

    return -min_cost_flow(graph, to, cap, cost, 0, size - 1, k)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)
    grid = [[next(data) for _ in range(n)] for _ in range(n)]
    print(0 if k == 0 else max_gain(grid, k))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：建图 $O(N^2)$，初始势 $O(N^2)$，每次 Dijkstra $O(N^2 \log N)$，共 $K$ 轮， 合计 $O(KN^2 \log N)$。$N=50, K=10$ 时点数 $2N^2 = 5000$、弧数约 $2\times10^4$， 实测单点约 60ms。
• 空间复杂度：弧数组与邻接表 $O(N^2)$，每轮 Dijkstra 的距离数组与堆 $O(N^2)$，合计 $O(N^2)$。

对比：朴素贪心是 $O(KN^2)$ 但结果错误；$K$ 维联合 DP 是 $O(N^{2K})$ 不可行。 费用流把 $K$ 从状态维度搬到了流量上，只多付 $K$ 倍的增广开销，这是本题唯一可行的多项式做法。

总结

本题的关键是把"每格只计一次分"翻译成"容量 1 的弧"。

• 朴素贪心（逐条取最大权路径）在样例规模上很快，但它是短视的：第一条路径可能独占掉 对后续路径更有价值的格子。上面 $N=3,K=2$ 的反例里贪心 $19$、最优 $20$。
• 把 $K$ 条路径并排塞进 DP 状态是 $O(N^{2K})$，$K=10$ 时不可行。
• 换个角度看计分规则——"第一次经过拿分、之后经过免费"本来就是一条容量规则， 于是拆点建图：计分弧容量 1 费用 $-a$，借道弧容量 $K$ 费用 $0$，移动弧容量 $K$ 费用 $0$， 跑 $K$ 轮最小费用增广，答案取负。
• 计分弧费用为负，Dijkstra 必须配势能；由于拆点后的点编号天然是 DAG 拓扑序， 初始势可以用一遍 $O(V+E)$ 的最短路递推求出，比 SPFA 更稳。

图示解析

下面这张图串起从"路径并集"到"费用流答案"的主线：

1
2
3
4
5
6
7
8
9输入 N, K, 网格 a
`- 朴素贪心：每条路径独立取最大权
   `- 反例：第一条路独占好格子，合计 19 < 最优 20
      `- 瓶颈：K 条路径必须联合决策
         |- 塞进 DP 状态  -> O(N^(2K)) 不可行
         `- 改成流量模型  -> 每格"计分机会"容量为 1
            `- 拆点：入点 --cap1,-a--> 出点 --capK,--0--> 右/下邻居
               `- 初始势 = 源点最短路（点编号即拓扑序）
                  `- K 轮 Dijkstra 增广，取费用相反数 = 答案

先看"瓶颈"那一层：它解释了为什么必须改用流量模型，而不是把 DP 维数继续加大。 再看"拆点"那一层：容量 1 的计分弧与容量 $K$ 的借道弧是平行的， 这正是"同一格只算一次"的完整实现。最后一行说明 $K$ 只影响增广轮数，不影响图的规模。

在样例上，第一轮增广走 $(0,0)\to(0,1)\to(1,1)\to(2,1)\to(2,2)$ 拿到 $11$， 第二轮走 $(0,0)\to(0,1)\to(0,2)\to(1,2)\to(2,2)$，其中 $(0,0),(0,1),(2,2)$ 已走过、改走借道弧， 新增 $3+1=4$，合计 $15$，与题面输出一致。