问题理解

我们有：

• $n$ 类产品，第 $i$ 类需要 $C_i$ 件
• $m$ 名员工，员工 $i$ 能制造产品 $j$ 当且仅当 $A_{i,j} = 1$
• 每个员工的愤怒值是分段线性函数：制造第 $k$ 件产品的边际愤怒值 $W_{i,j}$ 随 $k$ 所在区间变化，且 $W_{i,j}$ 单调递增

目标：将产品合理分配给员工，满足所有需求，并最小化总愤怒值。

关键观察

1. 问题本质
   这是一个带约束的资源分配问题，可建模为最小费用流：

   • 流：产品制造数量
   • 费用：员工的愤怒值增量
   • 约束：每个产品类别的总产量 = $C_i$，员工只能生产允许的产品类型

2. 分段线性费用处理
   对于员工 $i$，若其生产 $x$ 件产品，总愤怒值为： [ f_i(x) = \sum_{j=1}^{S_i+1} \min(x - T_{i,j-1},\ T_{i,j} - T_{i,j-1})^+ \cdot W_{i,j} ] 其中 $(z)^+ = \max(z,0)$。
   由于 $W_{i,j}$ 递增，这个函数是凸的，因此可以在流网络中通过多条边表示。

网络流建模

节点设计

1. 源点 $S$
2. 产品类型节点 $P_1, P_2, \dots, P_n$
3. 员工节点 $E_1, E_2, \dots, E_m$
4. 员工分段节点：每个员工 $i$ 拆成 $S_i+1$ 个节点 $F_{i,1}, F_{i,2}, \dots, F_{i,S_i+1}$
5. 汇点 $T$

边与容量/费用

1. $S \to P_j$：容量 $C_j$，费用 $0$（产品需求）
2. $P_j \to E_i$：若 $A_{i,j}=1$，容量 $+\infty$，费用 $0$（员工可生产该产品）
3. $E_i \to F_{i,k}$：容量 $T_{i,k} - T_{i,k-1}$，费用 $W_{i,k}$（分段区间）
4. $F_{i,k} \to T$：容量 $+\infty$，费用 $0$（汇点收集所有产品）

为什么这样建模正确

• 从 $S$ 流出的总流量 = $\sum C_j$，保证所有需求被满足
• 员工 $i$ 生产的产品先进入 $E_i$，然后按费用从低到高的顺序填充分段节点
• 由于 $W_{i,k}$ 递增，最小费用流会自动先使用便宜的分段，符合实际情况
• 分段容量限制确保不会在达到 $T_{i,k}$ 之前使用更贵的分段

算法步骤

1. 建图：按上述结构建立网络流图
2. 运行最小费用最大流算法（如 SSP、Primal-Dual）
3. 检查是否满流：若最大流 < $\sum C_j$，则无解（但题目保证有解，因 $1\times 1$ 分配总是可行）
4. 输出总费用：即最小愤怒值之和

复杂度分析

• 节点数：$O(m \cdot \max S_i + n + 2) \approx O(1500)$（$m,n \leq 250, S_i \leq 5$）
• 边数：$O(mn + m \cdot \max S_i) \approx O(10^5)$
• 使用基于 SPFA 的 SSP 算法或 Primal-Dual 算法，在这样规模的图上可行

样例验证

样例：

2 3
2 2 2
1 1 0
0 0 1
1
2
1 10
1
2
1 6

建图解释：

• 员工1：可生产产品1,2；分段：[1-2]费用1，[3-∞]费用10
• 员工2：可生产产品3；分段：[1-2]费用1，[3-∞]费用6

最优分配：

• 员工1生产2件产品1 → 费用 $1+1=2$
• 员工1生产2件产品2 → 费用 $1+1=2$
• 员工2生产2件产品3 → 费用 $1+1=2$

总费用 = $2+2+2=6$？
等等，样例输出是 24，说明我理解有误。

重新理解：
样例中员工1的分段是：第一段生产1~2件时每件费用1，之后每件费用10。
如果员工1生产4件，总费用 = $2\times 1 + 2\times 10 = 22$
员工2生产2件，总费用 = $2\times 1 = 2$
总和 = 24，符合输出。

这说明费用是分段累计的，不是每件单独算。网络流建模时，$E_i \to F_{i,k}$ 的费用设为 $W_{i,k}$ 会让算法自动累加。

总结

这道题的核心是：

1. 识别出最小费用流模型
2. 利用凸分段线性函数的性质，通过多条边表示
3. 正确设置容量和费用，使得流按费用从低到高使用分段
4. 保证所有产品需求被满足（满流）

通过将实际问题转化为流网络，可以高效求出全局最优解。