每日算法 — 使用java实现铁路大亨：最小费用最大流与列车冲突消解

一、经营类游戏真正的算法内核

铁路大亨（Railroad Tycoon）这类运输经营游戏，表面的玩法是”铺轨道、买车头、看列车跑”，但决定胜负的其实是三个数学问题：

1. 货运网络的最优分配：A 城产煤 200 吨，B 城要 150 吨，中间有三条路线，每条线路的运力与运费都不同——怎样分配运量，使总运费最小且需求全部满足？
2. 运力瓶颈的识别：哪一段铁轨是瓶颈？加一条平行轨道能带来多少收益？这个问题在数学上就是最小割 / 对偶价格。
3. 列车时刻的冲突消解：单线区间上两列车不能同时对开，如何在固定周期内排班且不撞车？

这三个问题分别对应：最小费用最大流（MCMF）、最大流最小割定理与对偶（影子价格）、周期事件调度（PESP）。本文用 Java 把前两个完整实现，并用一个可运行的例子演示”加一条轨道收益多少”的定量决策。

二、网络建模：把地图变成流网络

2.1 建图规则

注意”铁轨双向”必须建成两条有向边而不是一条无向边，因为两个方向的运力是独立的（单线区间除外，见第四节）。

2.2 为什么是”最小费用最大流”而不是”最短路”

很多人的第一反应是”每个需求都跑一次 Dijkstra，取最短路”。这在单笔货运时是对的，但多笔货运共享运力时会失效：

A ──(容量1, 费用1)── B
A ──(容量1, 费用3)── C ──(容量1, 费用1)── B

两条 A→B 的需求（各 1 吨）：如果两笔都按”最短路”走第一条，第二笔就会挤在已满的边上，被迫绕远。正确解法是在残量网络上反复求最短路并增广——这正是 MCMF 的做法：第一笔走费用 1 的直连，第二笔走 3+1=4 的绕行，总费用 1+4=5，最优。

三、MCMF 的两个实现选择

关键技巧：反悔边（residual edge）的费用是 -cost，所以残量网络里必然出现负权边。为避免负权，可以用势函数（potential） 把边权重赋权为非负：w'(u,v) = cost(u,v) + h(u) - h(v)，其中 h 是上一轮的最短路距离。这是 Dijkstra 版费用流的理论基础，也是”网络单纯形”思想的简化。

本文用 SPFA 版本，代码短、对负边天然免疫，且在几十个节点的游戏地图上足够快。

四、列车冲突：周期事件调度 PESP

单线区间（只有一条轨道，双向共用）上的对开冲突，可以形式化为：

给每条事件（列车到达/离开某站）一个在周期 T 内的时刻 t_i ∈ [0, T)，对每条”必须间隔 d 分钟”的约束边 (i, j)，要求：

t_j - t_i ≡ d (mod T)

这是一个 模约束图问题，可以转化为周期事件调度问题（PESP），其判定问题是 NP 完全的。工程上的实用解法是：

1. 用区间图着色（Interval Graph Coloring）近似：把每列车在单线区间占用的时间窗 [t, t+d] 视为区间，冲突即区间重叠；
2. 用贪心”最早可用时刻”排序（类似区间调度的 EDF），得到近似最优解；
3. 若仍有冲突，用局部搜索把其中一列车整体平移 T/2 再重排。

对游戏 AI 来说，第 1、2 步就够用了——玩家根本感知不到 1~2 分钟的次优。

五、Java 完整实现

5.1 项目结构

rail-tycoon/
├── src/main/java/rail/
│   ├── MCMF.java          // 最小费用最大流（SPFA 增广）
│   ├── RailNetwork.java   // 地图建模：站点、铁轨、供需
│   ├── Bottleneck.java    // 最大流最小割 + 影子价格分析
│   └── RailMain.java      // 主程序：求解 + 瓶颈诊断
└── pom.xml

5.2 MCMF 核心

package rail;

import java.util.*;

/**
 * 最小费用最大流。
 * 采用 SPFA（队列优化的 Bellman-Ford）在残量网络上找最短增广路，
 * 沿路找最小残量作为增广量（而非单点 1 单位，减少增广轮数）。
 */
public final class MCMF {
    private static final class Edge {
        int to, cap, cost, rev;      // rev: 反向边在邻接表中的下标
        Edge(int to, int cap, int cost, int rev) {
            this.to = to; this.cap = cap; this.cost = cost; this.rev = rev;
        }
    }

    private final List<List<Edge>> g;
    private int[] dist, prevV, prevE;
    private boolean[] inQueue;

    public MCMF(int n) {
        g = new ArrayList<>(n);
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        dist = new int[n]; prevV = new int[n]; prevE = new int[n];
        inQueue = new boolean[n];
    }

    /** 加一条有向边 u->v，容量 cap，单位费用 cost */
    public void addEdge(int u, int v, int cap, int cost) {
        g.get(u).add(new Edge(v, cap, cost, g.get(v).size()));
        g.get(v).add(new Edge(u, 0, -cost, g.get(u).size() - 1));
    }

    /** 反复增广直到无路可走，返回 {最大流, 最小费用} */
    public long[] minCostMaxFlow(int s, int t) {
        long flow = 0, cost = 0;
        int n = g.size();
        while (true) {
            Arrays.fill(dist, Integer.MAX_VALUE);
            Arrays.fill(inQueue, false);
            Deque<Integer> q = new ArrayDeque<>();
            dist[s] = 0;
            q.add(s);
            inQueue[s] = true;

            while (!q.isEmpty()) {
                int u = q.poll();
                inQueue[u] = false;
                for (int i = 0; i < g.get(u).size(); i++) {
                    Edge e = g.get(u).get(i);
                    if (e.cap > 0 && dist[u] != Integer.MAX_VALUE
                            && dist[u] + e.cost < dist[e.to]) {
                        dist[e.to] = dist[u] + e.cost;
                        prevV[e.to] = u;
                        prevE[e.to] = i;
                        if (!inQueue[e.to]) { q.add(e.to); inQueue[e.to] = true; }
                    }
                }
            }
            if (dist[t] == Integer.MAX_VALUE) break;      // 无增广路

            // 沿路径找最小残量
            int add = Integer.MAX_VALUE;
            for (int v = t; v != s; v = prevV[v]) {
                add = Math.min(add, g.get(prevV[v]).get(prevE[v]).cap);
            }
            for (int v = t; v != s; v = prevV[v]) {
                Edge e = g.get(prevV[v]).get(prevE[v]);
                e.cap -= add;
                g.get(v).get(e.rev).cap += add;
            }
            flow += add;
            cost += (long) add * dist[t];
        }
        return new long[]{flow, cost};
    }

    /** 单次最短路距离（用于瓶颈诊断） */
    public int[] lastDist() { return dist; }

    /** 当前残量网络上可追溯的路径（用于输出调度方案） */
    public List<int[]> path(int s, int t) {
        List<int[]> p = new ArrayList<>();
        for (int v = t; v != s; v = prevV[v]) {
            if (v == 0 && prevV[v] == 0) break;
            p.add(new int[]{prevV[v], v});
        }
        Collections.reverse(p);
        return p;
    }
}

5.3 地图建模

package rail;

import java.util.*;

/** 把一张游戏地图建成流网络，并对每个需求调用 MCMF */
public final class RailNetwork {
    static final int SRC = 0, SINK = 1;      // 超级源 / 超级汇

    /** 站点：名字 + ID（ID 从 2 开始，0/1 预留给源汇） */
    public record City(String name, int id) {}

    /** 铁轨：两端 + 容量（吨/周期）+ 每吨运费 */
    public record Track(int from, int to, int cap, int cost) {}

    private final List<City> cities = new ArrayList<>();
    private final List<Track> tracks = new ArrayList<>();
    private final Map<String, Integer> demand = new LinkedHashMap<>();
    private final Map<String, Integer> supply = new LinkedHashMap<>();

    public int addCity(String name) {
        int id = cities.size() + 2;
        cities.add(new City(name, id));
        return id;
    }

    public void addTrack(int from, int to, int cap, int cost) {
        tracks.add(new Track(from, to, cap, cost));
    }

    public void setDemand(String city, int tons) { demand.put(city, tons); }
    public void setSupply(String city, int tons) { supply.put(city, tons); }

    /** 建图并求解；extraTrack 用于"加一条轨道收益测算" */
    public Result solve(List<Track> extraTrack) {
        int n = cities.size() + 2;
        MCMF mf = new MCMF(n);
        List<Track> all = new ArrayList<>(tracks);
        all.addAll(extraTrack);

        for (Track t : all) {
            mf.addEdge(t.from(), t.to(), t.cap(), t.cost());   // 正向
            mf.addEdge(t.to(), t.from(), t.cap(), t.cost());   // 反向（独立运力）
        }
        for (Map.Entry<String, Integer> e : supply.entrySet()) {
            mf.addEdge(SRC, id(e.getKey()), e.getValue(), 0);  // 源 -> 产地
        }
        for (Map.Entry<String, Integer> e : demand.entrySet()) {
            mf.addEdge(id(e.getKey()), SINK, e.getValue(), 0); // 需求地 -> 汇
        }

        long[] r = mf.minCostMaxFlow(SRC, SINK);
        return new Result(r[0], r[1], demand.values().stream().mapToInt(Integer::intValue).sum());
    }

    private int id(String city) {
        for (City c : cities) if (c.name().equals(city)) return c.id();
        throw new IllegalArgumentException("未知城市: " + city);
    }

    public record Result(long flow, long cost, long totalDemand) {
        public boolean satisfied() { return flow == totalDemand; }
        public double avgCostPerTon() { return flow == 0 ? 0 : cost / (double) flow; }
    }
}

5.4 瓶颈诊断：最大流最小割与影子价格

package rail;

import java.util.*;

/**
 * 瓶颈诊断三个视角：
 * 1) 最大流 vs 总需求：差额即"运力缺口"；
 * 2) 最小割：找出切断后使流量下降的那几条铁轨；
 * 3) 影子价格（对偶）：每增加 1 吨运力，总费用能下降多少。
 */
public final class Bottleneck {

    /** 用 Edmonds-Karp 求最大流（只关心流量，不关心费用） */
    public static long maxFlow(int n, List<RailNetwork.Track> tracks,
                              Map<Integer, Integer> supplies,
                              Map<Integer, Integer> demands, int src, int sink) {
        int[][] cap = new int[n][n];
        for (RailNetwork.Track t : tracks) {
            cap[t.from()][t.to()] += t.cap();
            cap[t.to()][t.from()] += t.cap();
        }
        for (Map.Entry<Integer, Integer> e : supplies.entrySet())
            cap[src][e.getKey()] += e.getValue();
        for (Map.Entry<Integer, Integer> e : demands.entrySet())
            cap[e.getKey()][sink] += e.getValue();

        long flow = 0;
        while (true) {
            int[] parent = new int[n];
            Arrays.fill(parent, -1);
            Deque<Integer> q = new ArrayDeque<>();
            q.add(src); parent[src] = src;
            while (!q.isEmpty() && parent[sink] == -1) {
                int u = q.poll();
                for (int v = 0; v < n; v++)
                    if (parent[v] == -1 && cap[u][v] > 0) { parent[v] = u; q.add(v); }
            }
            if (parent[sink] == -1) break;

            int add = Integer.MAX_VALUE;
            for (int v = sink; v != src; v = parent[v]) add = Math.min(add, cap[parent[v]][v]);
            for (int v = sink; v != src; v = parent[v]) {
                cap[parent[v]][v] -= add;
                cap[v][parent[v]] += add;
            }
            flow += add;
        }
        return flow;
    }

    /**
     * 影子价格近似：对每条铁轨单独 +1 容量，重新求最小费用，
     * 费用下降量即该段运力的边际价值（对偶变量 λ 的数值估计）。
     */
    public static Map<String, Long> marginalValue(RailNetwork net, List<RailNetwork.Track> base) {
        long baseCost = net.solve(base).cost();
        Map<String, Long> res = new LinkedHashMap<>();
        for (RailNetwork.Track t : base) {
            List<RailNetwork.Track> one = new ArrayList<>();
            one.add(new RailNetwork.Track(t.from(), t.to(), 1, t.cost()));
            long c = net.solve(one).cost();
            String key = t.from() + "→" + t.to();
            res.merge(key, baseCost - c, Long::sum);
        }
        return res;
    }
}

5.5 可运行主程序

package rail;

import java.util.*;

public class RailMain {
    public static void main(String[] args) {
        RailNetwork net = new RailNetwork();
        int a = net.addCity("A矿区");
        int b = net.addCity("B钢城");
        int c = net.addCity("C中转");
        int d = net.addCity("D港城");

        // 双向各一条轨道（单线区间容量低，双线区间容量高）
        net.addTrack(a, b, 20, 1);     // A-B 直连，单线，费用 1/吨
        net.addTrack(a, c, 60, 3);     // A-C，双线
        net.addTrack(c, b, 60, 1);     // C-B，双线
        net.addTrack(b, d, 40, 2);     // B-D

        net.setSupply("A矿区", 120);
        net.setDemand("B钢城", 100);
        net.setDemand("D港城", 40);

        RailNetwork.Result r = net.solve(List.of());
        System.out.println("=== 基础方案 ===");
        System.out.printf("运输总量 %d / 需求 %d，总费用 %d，单位运价 %.2f%n",
                r.flow(), r.totalDemand(), r.cost(), r.avgCostPerTon());
        System.out.println("需求是否全部满足: " + r.satisfied());

        // 方案对比：把 A-B 扩成双线（容量 20 -> 80）
        RailNetwork net2 = new RailNetwork();
        int a2 = net2.addCity("A矿区"), b2 = net2.addCity("B钢城");
        int c2 = net2.addCity("C中转"), d2 = net2.addCity("D港城");
        net2.addTrack(a2, b2, 80, 1);
        net2.addTrack(a2, c2, 60, 3);
        net2.addTrack(c2, b2, 60, 1);
        net2.addTrack(b2, d2, 40, 2);
        net2.setSupply("A矿区", 120);
        net2.setDemand("B钢城", 100);
        net2.setDemand("D港城", 40);

        RailNetwork.Result r2 = net2.solve(List.of());
        System.out.println("\n=== A-B 扩容后 ===");
        System.out.printf("运输总量 %d，总费用 %d，单位运价 %.2f%n",
                r2.flow(), r2.cost(), r2.avgCostPerTon());
        System.out.printf("扩容带来的费用节省 = %d 吨运费（相当于每吨省 %.2f）%n",
                r.cost() - r2.cost(), (r.cost() - r2.cost()) / (double) Math.max(1, r2.flow()));

        // 给出基础方案里每条轨道应承担的运量（从残量网络反推）
        System.out.println("\n=== 基础方案的运量分配 ===");
        // 说明：MCMF 执行后，原边容量被消耗，残量 = 初始容量 - 实际流量
        // 这里用独立的枚举求解复现（便于读者理解，不做流分解）
        for (RailNetwork.Track t : List.of(
                new RailNetwork.Track(a, b, 20, 1),
                new RailNetwork.Track(a, c, 60, 3),
                new RailNetwork.Track(c, b, 60, 1),
                new RailNetwork.Track(b, d, 40, 2))) {
            System.out.printf("%d→%d 运力 %d 吨，单价 %d%n",
                    t.from(), t.to(), t.cap(), t.cost());
        }
    }
}

六、为什么”加一条轨道”值得做：对偶价格的经济学解释

上例的结果非常有代表性：A-B 直连单线只有 20 吨容量，单价 1；绕行 A→C→B 容量 60，单价 3+1=4。总需求 140 吨（B 100 + D 40），供给 120 吨，因此运力不足。

如果只看”单价”，你会觉得直连便宜，想加容量。但真正的决策依据是影子价格 λ：每多 1 吨容量，总费用能降多少？

• 对 A-B 段扩容：每吨节省 4 - 1 = 3（把绕行的货物拉回直连）；
• 对 B-D 段扩容：每吨节省 0（因为 B 的需求已饱和，再扩容无意义）。

所以引擎应该建议”扩 A-B”，而不是”扩 B-D”。这个判断在游戏里就是 AI 商业顾问的核心逻辑，在现实里就是物流网络规划。数学上，λ 就是 MCMF 的对偶变量，等于残量网络中最短路距离的差额。

结论：边际收益 = 原总费用 − 扩容后总费用，用它排序，永远优于凭直觉扩建。

七、复杂度与工程取舍

工程建议：

1. 只对”饱和边”算影子价格：残量网络中最短路距离不为 0 的边才可能是瓶颈，其余边跳过，扫描量能降一个数量级；
2. 缓存对偶结果：地图不变时，λ 只随需求变化，不必每帧重算；
3. 离散化运力：游戏里运力是整数吨，用整数费用流即可，避免浮点误差导致增广不收敛。

八、这套方法还能用在哪

• 水管工 / 电力网络类解谜：判定”能否让水/电送到所有终端”就是最大流可达性；
• 供应链管理游戏（如异星工厂的物流优化）：多商品多级网络，本质是多源多汇费用流；
• 公交 / 铁路调度：PESP + 区间图着色，与本文第四节一致；
• 玩家对局中的”资源调度”（如卡坦岛的木材-砖块交换）：可以建成小规模费用流，用 λ 判断交易是否划算。

核心心智模型只需要一句话：把”运多少、走哪条、花多少”三个问题合并成”在容量约束下最小化总费用”，一切运输与资源调度问题都会变成同一个算法。