题目理解

我们有 $n$ 种数字，第 $i$ 种数字有：

• 数值：$a_i$
• 数量：$b_i$ 个
• 权值：$c_i$

配对规则：两个数字 $a_i$ 和 $a_j$ 可以配对，当且仅当：

1. $a_i$ 是 $a_j$ 的倍数
2. $a_i / a_j$ 是一个质数

配对收益：$c_i \cdot c_j$

限制条件：

• 每个数字只能参与一次配对
• 总收益（所有配对的价值和）不能小于 $0$
• 目标：最大化配对次数

---

问题分析

1. 配对关系的性质

如果 $a_i$ 是 $a_j$ 的倍数且 $a_i / a_j$ 是质数，意味着这两个数在质因数分解上只差一个质因子。

这实际上定义了一个二分图：

• 将数字按质因子个数奇偶性分成两类
• 只有不同类的数字才可能配对

2. 网络流建模

这是一个典型的最大权匹配问题，但有两个特殊之处：

• 有数量限制（$b_i$）
• 要求总权值 $\geq 0$ 的前提下最大化匹配数

我们可以用费用流来解决：

• 源点 → 左部节点：容量 $b_i$，费用 $0$
• 左部节点 → 右部节点：容量 $\infty$，费用 $-c_i \cdot c_j$（注意负号）
• 右部节点 → 汇点：容量 $b_i$，费用 $0$

3. 处理非负总收益约束

由于要求总收益 $\geq 0$，而费用流求的是最小费用，我们可以：

• 在 SPFA 增广时，如果当前累计费用 $> 0$ 就停止
• 因为费用是负的收益，费用 $> 0$ 意味着收益 $< 0$

---

算法设计

步骤 1：建图

1. 对每个数字分解质因数，按质因子个数奇偶性划分到左右两部
2. 对于所有满足配对条件的 $(i,j)$，连边：
   • 容量：$\min(b_i, b_j)$（实际上用 $\infty$ 更简单）
   • 费用：$-c_i \cdot c_j$

步骤 2：费用流求解

使用 SPFA 找最短路（最小费用路径）：

• 每次找到一条从源点到汇点的最短路
• 沿该路径增广 $\min$（路径容量，剩余流量）
• 记录当前总费用，如果总费用 $> 0$ 就停止
• 否则继续，直到无法增广

步骤 3：输出结果

最终匹配数就是最大流的值。

---

关键点分析

1. 二分图证明

设 $f(x)$ 表示 $x$ 的质因子个数（重复计算）。 如果 $a_i / a_j$ 是质数，那么 $f(a_i) = f(a_j) + 1$。 因此 $f(a_i)$ 和 $f(a_j)$ 奇偶性不同，构成二分图。

2. 费用流技巧

由于要求收益不小于 0，而费用流求的是最小费用，我们：

• 将收益的相反数作为费用
• 当累计费用 $> 0$（即收益 $< 0$）时停止

3. 复杂度分析

• 节点数：$O(n)$
• 边数：$O(n^2)$（最坏情况）
• 由于 $n \leq 200$，费用流可以接受

---

样例验证

输入：

3
2 4 8
2 200 7  
-1 -2 1

分析：

• $a = [2,4,8]$，$b = [2,200,7]$，$c = [-1,-2,1]$
• 配对关系：
  • 4/2=2(质数)：收益 $(-2)\times(-1)=2$
  • 8/4=2(质数)：收益 $1\times(-2)=-2$
  • 8/2=4(非质数)：不能配对

最优方案：

• 2个2与2个4配对：收益 $2\times2=4$
• 2个4与2个8配对：收益 $2\times(-2)=-4$
• 总收益 $0$，总配对次数 $4$

输出：4 ✓

---

总结

本题的关键在于：

1. 发现配对关系构成二分图
2. 用费用流求解最大匹配
3. 通过控制费用流停止条件来保证总收益非负
4. 注意质数判断和质因数分解的实现

算法复杂度：$O(n^2 \cdot \text{流大小})$，在 $n \leq 200$ 时可行。