定义：连通带权图的所有生成树中，权值和最小的那棵（包含图中所有顶点）。边数 = 顶点数 − 1。
| 算法 | 思路 | 适合 |
|---|---|---|
| Prim 普里姆 | 从某顶点出发，每次选一条"树内→树外"的最小权边扩展顶点 | 稠密图 |
| Kruskal 克鲁斯卡尔（教材推荐常用） | 把所有边按权从小到大依次尝试加入，形成闭环则舍弃，直到连接所有顶点 | 稀疏图；手工计算首选 |
手算模板（教材例：6 城市，边 AE=FD=200，AB=BF=AF=CD=400……）：① 排序所有边权；② 依次取最短边，不构成环就保留；③ 凑够"顶点数−1"条边即止；④ 注意题目可能问"最少的方案共有几个"——权值相同的边可互换，会产生多个并列最优解（例题答案：总长 200+200+400+400+400=1600，共 3 种方案）。
核心规则：总的最大流量 = 各条路径最大流量之和；每条路径的最大流量 = 该路径各段流量的最小值（短板效应）。
手算模板（教材例答案 23 万吨/小时）：
定义：在有限资源条件下，如何有效使用资源达到预定目标——一组约束条件下求目标表达式的极值。常用解法：图解法、联立方程组法。
| 解法 | 步骤与特点 |
|---|---|
| 图解法 | ① 把每个不等式画成直线；② 判定不等号方向确定解区间（可行域）；③ 目标函数 N=ax+by 表现为一组平行等值线族，沿梯度方向平移至可行域顶点取最优。直观、不丢正解；计算量 O(n)；适合约束少、2 个变量的情况 |
| 联立方程组法 | 两两联立约束方程求交点，代入所有不等式检验可行性，再代入目标函数比大小；可能丢失正解（最优解在 X 轴/Y 轴交点上时）；计算量 O(n²)；3 个及以上变量时的主要方法 |
整数要求：数学最优解若含小数（如 10/3 套），而题意要求整数 → 向可行域内取整再验证（教材例：P₂(2,10/3) 与 P₃(1,4) 同在等值线 N=14 上，因 x,y 须为整数取 P₃ → 利润最大 14 万元，答案 B）。
解的 4 种可能：① 唯一最优解——在解区间多边形的某个顶点上；② 无穷多最优解——找到两个不同最优解则必有无穷多个；③ 无界解——有无穷多解但无最优解（缺少必要约束）；④ 无可行解——约束条件互相矛盾。
定义：把问题实例分解为更小的相似子问题，存储子问题的解避免重复计算，以解决最优化问题。装货最大价值问题速解：先算每种货物的单位利润 = 每件利润 ÷ 每件重量，按单位利润从高到低装，装不下整件时装"剩余吨位内单位利润次高"的组合（教材例：载重 10 吨，D 单位利润 54 元/吨最高装 2 件 8 吨，剩 2 吨装 A 两件 → 2×216+2×53=538 元，答案 D）。
EMV = Σ（每个可能结果的收益 × 发生概率）；比较各方案 EMV 取优。常与决策树相辅相成。解题技巧：决策树在最左边做决策，所以要从右向左逐层计算化简。
教材例（水路 vs 陆路）：货物 9000 元，陆路成本恒 1000 元；水路一般 700 元、遇暴风雨损失 10%（900 元）+运费 700=1600 元，暴风雨概率 15% → 水路期望成本 = 700×85% + 1600×15% = 835 元 < 1000 元 → 选水路。
多级决策树（教材例：大厂 vs 小厂 7 年总收益）：先算最右端后 5 年各节点期望值（按销路概率加权×5 年），再算前 2 年期望值并扣除初期投资，比较总收益——建大厂 [200×0.7+(−20)×0.3]×2+(780×0.7+10×0.3)−500=317 万元 > 建小厂 288 万元 → 选建大厂（总收益略多于 300 万元）。
适用：无法估计各状态发生概率时，按决策者主观倾向决策。
| 准则 | 别名 | 决策原则 | 操作（以教材收益表为例） |
|---|---|---|---|
| 乐观主义准则 | 最大最大准则 | 大中取大 | 各方案先取最大收益，再从中取最大者 → 积极（500） |
| 悲观主义准则 | 最大最小准则 | 小中取大 | 各方案先取最小收益，再从中取最大者 → 保守（200） |
| 折中主义准则 | 乐观系数法 | α·最大收益 + (1−α)·最小收益 | 给乐观系数 α 加权调和（大纲提及） |
| 等可能性准则 | 拉普拉斯准则 | 各状态等概率取期望 | 每种状态概率 = 1/n，算平均收益取最大 |
| 后悔值准则 | 最小最大后悔值 | 大中取小（后悔值） | 见下方三步法 → 稳健（250） |
后悔值三步法（真题必会）：