「接金币」是个看起来不需要算法的游戏——左手右手一起动，见金币就扑上去。但只要加一个约束，它就变成一道标准的网络流问题：如果同时有 k 个接盘（或者 k 个玩家共享同一个关卡），怎样安排每个接盘的轨迹，才能收到最多金币？
答案不在贪心里，也不在 DP 里，而在时间扩展网络（Time-Expanded Network）上的最小费用流。本文用 Java 从零实现这套建模，并解释一个几乎所有人第一次写都会踩的坑：金币节点为什么必须拆点。
一、把「时间」变成一层网络
游戏里最麻烦的东西是时间：同一时刻你只能站在一个格子上，不同时刻的金币对你是「不同的机会」。处理这类问题的标准套路是把时间也展开成图的一维：
- 节点 = 「第 t 时刻位于格子 (r, c)」，共
T × rows × cols个； - 相邻时刻之间连边，代表「一步移动」：原地停留、左右平移、下移一行（含斜下）。
这样，一个「接盘的完整轨迹」就变成网络上从源点走到汇点的一条路径。这一步的关键转变是：
时间不再是循环里的变量，而是图的一层。轨迹规划 = 图上寻路。
一旦轨迹变成路径，「多个接盘分配金币」就自然变成「多流问题」——每条路径占一份流量，每个金币只能被一条路径收走。
二、金币怎么建模：拆点是唯一的正确解
初学者最自然的想法是：金币格就是一个节点，让路径经过它就算收下。但网络流不认「经过」，只认「容量」。所以金币必须变成一条有容量的边。
问题来了：节点本身没有容量，只有边才有。于是在节点上直接加「容量 1、费用 -1」的平行边，会形成这样的结构：
base ──→ in(1, -1)──→ out ──→ base ← 负环！
只要存在这条 base → in → out → base 的回路，且总费用为 -1，SPFA 就会不断沿这个环「绕圈」来降低费用，永远不收敛——程序直接卡死。这不是理论风险，本文的第一版实现就真的卡在这里，跑了 180 秒超时。
正确的做法是彻底拆点：把一个金币格拆成 in 和 out 两个节点，
- 所有入边接到
in； - 所有出边从
out引出； in → out之间放两条平行边：容量 1 费用 -1（第一个经过者得金币），容量 k-1 费用 0（后续经过者只是路过）。
for (int t = 1; t < TIME; t++)
for (int[] coin : COINS[t]) {
int r = coin[0], c = coin[1];
int in = addNode(), out = addNode();
inNode[t][r][c] = in; outNode[t][r][c] = out;
addEdge(in, out, 1, -1); // 第一个经过者得 1 金
if (k > 1) addEdge(in, out, k - 1, 0); // 其余经过者只能路过
}
拆点之后，移动边必须改成「从上一时刻的 out 连到下一时刻的 in」：
addEdge(outNode[t][r][c], inNode[t + 1][nxt[0]][nxt[1]], k, 0);
这一步改动只涉及两个数组索引，但它是整个实现从「卡死」到「正确」的分水岭。负环的根源永远是「同一个节点既是入口又是出口」。
三、求解：SPFA + 连续最短路
边权里出现了 -1，Dijkstra 失效（它要求非负权），所以用 SPFA 找每条增广路的最短路：
int[] minCostFlow(int s, int t, int maxFlow) {
while (totalFlow < maxFlow) {
Arrays.fill(dist, Integer.MAX_VALUE);
dist[s] = 0;
ArrayDeque<Integer> q = new ArrayDeque<>(); q.add(s);
while (!q.isEmpty()) { // SPFA：允许负权边
int v = q.poll(); inQ[v] = false;
for (Edge e : g.get(v)) {
if (e.residual() > 0 && dist[v] + e.cost < dist[e.to]) {
dist[e.to] = dist[v] + e.cost;
prevV[e.to] = v; prevE[e.to] = i;
if (!inQ[e.to]) { inQ[e.to] = true; q.add(e.to); }
}
}
}
if (dist[t] == Integer.MAX_VALUE) break; // 无增广路
// ... 沿 prevV/prevE 回退，更新流量 ...
}
return new int[]{totalFlow, totalCost};
}
这就是连续最短路算法（Successive Shortest Path）：每次增广「当前残量网络里最便宜的路径」。它的正确性依赖于一个重要性质——如果初始网络无负环，则每次增广后的残量网络仍无负环。这也是为什么第二节的拆点如此关键：有负环时这个前提直接崩塌。
复杂度 O(F · V · E)，本文的图只有百级节点、k ≤ 3，毫秒级完成。
四、用联合 DP 交叉验证
最小费用流的结果必须被独立验证，否则你无法区分「算法跑对了」和「文件跑完了」。
验证方法：k 条路径的联合状态 DP。状态是 k 条路径当前所在的格子（有序元组），逐层推演，每层统计落在金币格上的不同格子数：
static int jointDP(int k) {
// 状态 = k 条路径的有序位置组合
// 每层：对每个状态枚举所有后继组合，累加本层金币命中数
}
因为同一时刻不会有两个金币出现在同一格，这种「按不同格子计数」不会重复计算，所以联合 DP 的结果是精确基准。
实测三个规模的对比：
| k（接盘数） | 最小费用流收入 | 联合 DP 基准 | 一致 |
|---|---|---|---|
| 1 | 3 | 3 | 是 |
| 2 | 5 | 5 | 是 |
| 3 | 7 | 7 | 是 |
10 枚金币、3 个接盘只能收到 7 枚——剩下 3 枚是「时间-空间上真的赶不到」的。这些不可达的金币构成了关卡的真实难度上限。
五、单路径最优轨迹长什么样
对 k=1 再做一次 DP 回溯，能得到完整的轨迹（这也是游戏里「自动演示」功能需要的输出）：
t=0 (0,0) t=1 (1,1) t=2 (2,2) t=3 (2,2) t=4 (2,3)
t=5 (2,2) t=6 (2,1) t=7 (2,0)
收入 3 枚。注意 t=3 时它停在原地不动——这不是浪费一步，而是为了在 t=4 到 (2,3) 收金币、并在 t=5 及时折返。在时间扩展网络里，「原地停留」是一条正经的边（自环），不是「什么都不做」。 这一点在建模时极易漏掉：如果只连「移动」边不连「停留」边，路径被迫每步都必须移动，最优解就会算错。
六、完整可运行代码
项目结构：
coin-catcher-mincostflow/
├── src/
│ └── CoinCatcherMinCostFlow.java
└── out/
javac -d out src/CoinCatcherMinCostFlow.java
java -cp out CoinCatcherMinCostFlow
import java.util.*;
/**
* 「接金币」游戏的最优收集问题 —— 时间扩展网络上的最小费用流。
*
* 游戏设定：ROWS×COLS 网格，玩家控制 k 个接盘（k 个并行的分身），
* 每单位时间每个接盘可：原地停留、左右平移一格、或下移一行（可带左右偏移）。
* 每个时刻 t 会在若干个格子掉落金币，接盘恰好在 (t,r,c) 即可收下，每枚金币只能收一次。
*
* 建模（时间扩展网络 / Time-Expanded Network）：
* 节点 = 「第 t 时刻位于格子 (r,c)」，共 TIME×ROWS×COLS 个。
* 移动边：相邻时刻之间连容量 k、费用 0 的边。
* 金币节点必须「拆点」：把所有入边导入 in、所有出边从 out 引出，
* in → out 一条容量 1、费用 -1 的边，代表第一个经过者收走金币；
* in → out 一条容量 k-1、费用 0 的边，代表后续路径只是路过。
* 若不做拆点、只是在原节点上加平行边，会形成 base→in→out→base 的负环，
* SPFA 会无限松弛（这是实现这类模型最容易踩的坑）。
*
* 求解：连续最短路算法 + SPFA（边权含 -1，不能用 Dijkstra）。
* 复杂度 O(F·V·E)，图只有百级节点、k ≤ 3，毫秒级完成。
*
* 正确性用「k 条路径的联合状态 DP」交叉验证：
* 状态 = (t, 路径1位置, 路径2位置, ...)，逐层推演，每层统计落在金币格的不同位置数。
* 因为同一时刻不会有两个金币出现在同一格，联合 DP 的计数是无重复的，可作为精确基准。
*/
public final class CoinCatcherMinCostFlow {
static final class Edge {
int to, rev, cap, cost, flow;
Edge(int t, int r, int c, int w) { to = t; rev = r; cap = c; cost = w; }
int residual() { return cap - flow; }
}
final List<List<Edge>> g = new ArrayList<>();
int addNode() { g.add(new ArrayList<>()); return g.size() - 1; }
void addEdge(int u, int v, int cap, int cost) {
g.get(u).add(new Edge(v, g.get(v).size(), cap, cost));
g.get(v).add(new Edge(u, g.get(u).size() - 1, 0, -cost));
}
/** 连续最短路：SPFA 找最小费用增广路，直到流量达到 maxFlow */
int[] minCostFlow(int s, int t, int maxFlow) {
int n = g.size(), totalFlow = 0, totalCost = 0;
int[] dist = new int[n], prevV = new int[n], prevE = new int[n];
while (totalFlow < maxFlow) {
Arrays.fill(dist, Integer.MAX_VALUE);
dist[s] = 0;
boolean[] inQ = new boolean[n];
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(s); inQ[s] = true;
while (!q.isEmpty()) {
int v = q.poll(); inQ[v] = false;
for (int i = 0; i < g.get(v).size(); i++) {
Edge e = g.get(v).get(i);
if (e.residual() > 0 && dist[v] != Integer.MAX_VALUE
&& dist[v] + e.cost < dist[e.to]) {
dist[e.to] = dist[v] + e.cost;
prevV[e.to] = v; prevE[e.to] = i;
if (!inQ[e.to]) { inQ[e.to] = true; q.add(e.to); }
}
}
}
if (dist[t] == Integer.MAX_VALUE) break;
int add = maxFlow - totalFlow;
for (int v = t; v != s; v = prevV[v]) add = Math.min(add, g.get(prevV[v]).get(prevE[v]).residual());
for (int v = t; v != s; v = prevV[v]) {
Edge e = g.get(prevV[v]).get(prevE[v]);
e.flow += add;
g.get(v).get(e.rev).flow -= add;
}
totalFlow += add;
totalCost += add * dist[t];
}
return new int[]{totalFlow, totalCost};
}
// ---------------------- 关卡定义 ----------------------
static final int ROWS = 3, COLS = 4, TIME = 8;
/** coins[t] = 第 t 时刻的金币坐标 {row, col} */
static final int[][][] COINS = {
{}, // t=0 无金币
{{2, 1}}, // t=1
{{2, 0}, {2, 2}}, // t=2
{{1, 1}}, // t=3
{{1, 3}, {2, 3}}, // t=4
{{0, 2}}, // t=5
{{2, 1}}, // t=6
{{1, 0}, {1, 2}} // t=7
};
static int cell(int t, int r, int c) { return (t * ROWS + r) * COLS + c; }
/** 合法的下一位置：停留、左移、右移、下移（含斜下） */
static List<int[]> successors(int r, int c) {
List<int[]> out = new ArrayList<>();
out.add(new int[]{r, c}); // 停留
if (c > 0) out.add(new int[]{r, c - 1}); // 左移
if (c + 1 < COLS) out.add(new int[]{r, c + 1}); // 右移
if (r + 1 < ROWS) {
out.add(new int[]{r + 1, c});
if (c > 0) out.add(new int[]{r + 1, c - 1});
if (c + 1 < COLS) out.add(new int[]{r + 1, c + 1});
}
return out;
}
/**
* 构造时间扩展网络。金币节点做 in/out 拆点，移动边按拆点后的出入口连接，
* 从而彻底避免 base→in→out→base 的负环。
*/
int[] buildNetwork(int k) {
// 每个 (t,r,c) 先分配一个基础节点
int[][][] base = new int[TIME][ROWS][COLS];
for (int t = 0; t < TIME; t++)
for (int r = 0; r < ROWS; r++)
for (int c = 0; c < COLS; c++) base[t][r][c] = addNode();
// 金币格：拆成 in / out
int[][][] inNode = new int[TIME][ROWS][COLS];
int[][][] outNode = new int[TIME][ROWS][COLS];
for (int t = 0; t < TIME; t++)
for (int r = 0; r < ROWS; r++)
for (int c = 0; c < COLS; c++) { inNode[t][r][c] = base[t][r][c]; outNode[t][r][c] = base[t][r][c]; }
for (int t = 1; t < TIME; t++)
for (int[] coin : COINS[t]) {
int r = coin[0], c = coin[1];
int in = addNode(), out = addNode();
inNode[t][r][c] = in; outNode[t][r][c] = out;
addEdge(in, out, 1, -1); // 第一个经过者得 1 金
if (k > 1) addEdge(in, out, k - 1, 0); // 其余经过者只能路过
}
int S = addNode(), T = addNode();
// 移动边：从上一时刻的「出口」连到下一时刻的「入口」
for (int t = 0; t < TIME - 1; t++)
for (int r = 0; r < ROWS; r++)
for (int c = 0; c < COLS; c++)
for (int[] nxt : successors(r, c))
addEdge(outNode[t][r][c], inNode[t + 1][nxt[0]][nxt[1]], k, 0);
// 源点 → 第 0 时刻任意列入场（容量 k）
for (int c = 0; c < COLS; c++) addEdge(S, inNode[0][0][c], k, 0);
// 任意时刻结束都要能到汇点：这里统一从最后时刻的出口连汇点
for (int r = 0; r < ROWS; r++)
for (int c = 0; c < COLS; c++) addEdge(outNode[TIME - 1][r][c], T, k, 0);
return new int[]{S, T};
}
// ---------------------- 精确基准：k 条路径的联合状态 DP ----------------------
/**
* 联合 DP：state 是 k 条路径当前所在的格子（有序）。
* 逐层推演，每层统计「落在金币格的不同格子数」，累加即为总收入。
* 由于同一时刻不会出现两个金币同格，这种计数不会重复计算。
*/
static int jointDP(int k) {
List<int[]> starts = new ArrayList<>();
for (int c = 0; c < COLS; c++) starts.add(new int[]{0, c});
// 生成全部长度为 k 的有序起点组合
Map<String, Integer> cur = new HashMap<>();
List<int[]> combo = new ArrayList<>();
buildCombos(starts, k, 0, combo, cur);
for (int t = 1; t < TIME; t++) {
Map<String, Integer> next = new HashMap<>();
for (Map.Entry<String, Integer> e : cur.entrySet()) {
List<int[]> pos = parse(e.getKey());
List<List<int[]>> options = new ArrayList<>();
for (int[] p : pos) options.add(successors(p[0], p[1]));
List<int[]> picked = new ArrayList<>();
expand(options, 0, picked, pos, e.getValue(), t, next);
}
cur = next;
}
int best = 0;
for (int v : cur.values()) best = Math.max(best, v);
return best;
}
static void buildCombos(List<int[]> pool, int k, int depth, List<int[]> cur, Map<String, Integer> out) {
if (depth == k) { out.put(key(cur), 0); return; }
for (int[] p : pool) { cur.add(p); buildCombos(pool, k, depth + 1, cur, out); cur.remove(cur.size() - 1); }
}
static void expand(List<List<int[]>> options, int idx, List<int[]> picked,
List<int[]> base, int value, int t, Map<String, Integer> out) {
if (idx == options.size()) {
int gain = coinHits(picked, t);
String k2 = key(picked);
out.merge(k2, value + gain, Math::max);
return;
}
for (int[] p : options.get(idx)) {
picked.add(p);
expand(options, idx + 1, picked, base, value, t, out);
picked.remove(picked.size() - 1);
}
}
static int coinHits(List<int[]> positions, int t) {
Set<String> hit = new HashSet<>();
for (int[] p : positions)
for (int[] coin : COINS[t])
if (coin[0] == p[0] && coin[1] == p[1]) hit.add(p[0] + "," + p[1]);
return hit.size();
}
static String key(List<int[]> pos) {
StringBuilder sb = new StringBuilder();
for (int[] p : pos) sb.append(p[0]).append(',').append(p[1]).append('|');
return sb.toString();
}
static List<int[]> parse(String s) {
List<int[]> out = new ArrayList<>();
for (String part : s.split("\\|")) {
if (part.isEmpty()) continue;
String[] ab = part.split(",");
out.add(new int[]{Integer.parseInt(ab[0]), Integer.parseInt(ab[1])});
}
return out;
}
/** 单路径最优轨迹：DP 求最大收入并回溯路径 */
static void traceBestSinglePath() {
int[][][] dp = new int[TIME][ROWS][COLS];
int[][][] fromR = new int[TIME][ROWS][COLS];
int[][][] fromC = new int[TIME][ROWS][COLS];
for (int[] row : dp[0]) Arrays.fill(row, Integer.MIN_VALUE);
for (int c = 0; c < COLS; c++) dp[0][0][c] = 0;
for (int t = 0; t < TIME - 1; t++) {
for (int[] row : dp[t + 1]) Arrays.fill(row, Integer.MIN_VALUE);
for (int r = 0; r < ROWS; r++)
for (int c = 0; c < COLS; c++) {
if (dp[t][r][c] == Integer.MIN_VALUE) continue;
for (int[] nxt : successors(r, c)) {
int nr = nxt[0], nc = nxt[1];
int gain = 0;
for (int[] coin : COINS[t + 1]) if (coin[0] == nr && coin[1] == nc) gain = 1;
int v = dp[t][r][c] + gain;
if (v > dp[t + 1][nr][nc]) {
dp[t + 1][nr][nc] = v;
fromR[t + 1][nr][nc] = r; fromC[t + 1][nr][nc] = c;
}
}
}
}
int best = -1, br = 0, bc = 0;
for (int r = 0; r < ROWS; r++)
for (int c = 0; c < COLS; c++)
if (dp[TIME - 1][r][c] > best) { best = dp[TIME - 1][r][c]; br = r; bc = c; }
StringBuilder path = new StringBuilder();
int r = br, c = bc;
for (int t = TIME - 1; t >= 0; t--) {
path.insert(0, "t=" + t + " (" + r + "," + c + ") ");
if (t > 0) { int pr = fromR[t][r][c], pc = fromC[t][r][c]; r = pr; c = pc; }
}
System.out.println("\n单路径最优轨迹（收入 " + best + " 枚）：");
System.out.println(" " + path.toString().trim());
}
public static void main(String[] args) {
int total = 0;
System.out.println("关卡：" + ROWS + " 行 × " + COLS + " 列，" + TIME + " 个时刻");
for (int t = 1; t < TIME; t++)
for (int[] coin : COINS[t]) {
total++;
System.out.println(" t=" + t + " 金币 (" + coin[0] + "," + coin[1] + ")");
}
System.out.println("金币总数 = " + total);
System.out.println("\nk | 最小费用流收入 | 联合DP基准 | 一致");
for (int k = 1; k <= 3; k++) {
CoinCatcherMinCostFlow mf = new CoinCatcherMinCostFlow();
int[] st = mf.buildNetwork(k);
int[] res = mf.minCostFlow(st[0], st[1], k);
int gain = -res[1];
int dp = jointDP(k);
System.out.printf("%d | %d | %d | %s%n", k, gain, dp, gain == dp ? "是" : "否");
}
traceBestSinglePath();
}
}
运行输出（节选）：
关卡：3 行 × 4 列，8 个时刻
t=1 金币 (2,1)
t=2 金币 (2,0)
...
金币总数 = 10
k | 最小费用流收入 | 联合DP基准 | 一致
1 | 3 | 3 | 是
2 | 5 | 5 | 是
3 | 7 | 7 | 是
单路径最优轨迹（收入 3 枚）：
t=0 (0,0) t=1 (1,1) t=2 (2,2) t=3 (2,2) t=4 (2,3) t=5 (2,2) t=6 (2,1) t=7 (2,0)
七、复杂度与关卡设计上的用途
| 项目 | 数值 | 说明 |
|---|---|---|
| 节点数 | T × rows × cols + 金币拆点 × 2 | 本文 96 + 20 ≈ 百级 |
| 边数 | 每层约 rows×cols×7 条移动边 | 含停留与三条下落 |
| 求解复杂度 | O(F · V · E) | SPFA 版常数为 V 倍 |
| 本文实测 | 毫秒级 | 三档 k 各一次 |
最小费用流的真正价值不只是「算出答案」，而是它同时给出了关卡的设计诊断。同一套网络只要改一行——把费用从 -1 改成 0——就变成纯最大流，可以在不求解的情况下算出「这个关卡理论上最多能收多少」，用 0.1 秒给上百个候选关卡打分。这就是关卡自动生成器的工作方式：先用最大流做可行性剪枝，再用最小费用流做最优性评分。
延伸方向：
- 用势函数 + Dijkstra 替换 SPFA。Johnson 势能可以把负权边转成非负，之后用 Dijkstra，复杂度降到 O(F · E log V)，适合节点数上千的大关卡。
- 把金币容量从 1 提升为「连续收益」。如果金币有不同面值，把费用从 -1 改成 -value，模型几乎不用改——这正是最小费用流比最大流更适合游戏数值设计的原因。
八、小结
接金币这道小游戏，在加了「k 个接盘」这个约束之后，就变成了时间扩展网络上的最小费用流。整套建模只有三个要点：
- 时间展开成图层，轨迹变成路径；
- 金币拆点，用「容量 1 费用 -1 + 容量 k-1 费用 0」表达「只能被收一次」；
- 停留也是一条边，否则最优解会被系统性低估。
而那个让第一版程序卡死 180 秒的负环，恰恰提醒了我们一件事：网络流建模的错误从来不会给出「差一点的答案」，它要么精确正确，要么彻底死循环。所以每一版都必须用联合 DP 这样的独立基准去校验——本文三档 k 全部一致，才敢说这套模型是对的。
