问题分析

我们有：

• $m$ 个仓库，第 $i$ 个仓库有 $a_i$ 单位货物
• $n$ 个商店，第 $j$ 个商店需要 $b_j$ 单位货物
• 供需平衡：$\sum a_i = \sum b_j$
• 从仓库 $i$ 到商店 $j$ 的单位运费为 $c_{ij}$

目标：

1. 求最小总运输费用
2. 求最大总运输费用

网络流建模

这是一个标准的二分图运输模型：

建图方法

1. 源点 $S$ 向每个仓库 $i$ 连边：

   • 容量 = $a_i$，费用 = $0$

2. 每个仓库 $i$ 向每个商店 $j$ 连边：

   • 容量 = $+\infty$，费用 = $c_{ij}$

3. 每个商店 $j$ 向汇点 $T$ 连边：

   • 容量 = $b_j$，费用 = $0$

算法步骤

最小费用

1. 按上述方法建图
2. 运行最小费用最大流算法
3. 输出总费用

最大费用

1. 建图时将所有费用 $c_{ij}$ 取负值（即费用 = $-c_{ij}$）
2. 运行最小费用最大流算法（此时求的是原问题的最大费用）
3. 输出总费用的相反数

或者直接使用支持最大费用流的算法。

样例验证

输入：

2 3
220 280
170 120 210
77 39 105
150 186 122

数据：

• 仓库货物：$a_1=220, a_2=280$，总量500
• 商店需求：$b_1=170, b_2=120, b_3=210$，总量500
• 运费矩阵：

  77   39  105
  150 186  122
  

最小费用流结果：48500
最大费用流结果：69140

复杂度分析

• 节点数：$m + n + 2 \leq 202$
• 边数：$m + n + m \times n \leq 100 + 100 + 10000 = 10200$
• 使用SSP（Successive Shortest Path）或Primal-Dual算法：
  • 复杂度约 $O(f \cdot E \cdot \text{最短路复杂度})$
  • 在 $m,n \leq 100$ 时完全可行

算法实现细节

最小费用流常用算法：

1. SSP算法（基于Bellman-Ford）
2. Primal-Dual算法（基于Dijkstra）
3. 容量缩放算法

由于可能存在负费用边（在最大费用流转换时），使用基于Bellman-Ford的SSP算法更稳妥。

关键点说明

1. 供需平衡保证存在可行流
2. 容量无穷大表示仓库可以向任意商店运输任意数量货物（只要不超仓库库存和商店需求）
3. 最小费用流直接求解最小运输成本
4. 最大费用流通过费用取负转化为最小费用流问题

总结

这道题是网络流中运输问题的标准模型：

• 通过二分图结构连接仓库和商店
• 用容量限制表示供应量和需求量
• 用边费用表示运输成本
• 分别计算最小费用流和最大费用流来得到两种极值情况

这是费用流在最优化问题中的经典应用。