题目描述
给定 $n$ 组数据，每组包含三个整数 $(a_i, b_i, c_i)$。对于任意两组数据 $i, j$，若 $\max(a_i, a_j) / \min(a_i, a_j)$ 为质数，则可以将 $i, j$ 配对，每次配对消耗双方各 1 个单位数量，获得 $c_i + c_j$ 的收益；每个数字最多使用 $b_i$ 次。求最大总收益。
读题分析
这道题需要配对，每对有权值，目标是让总权值最大。读题后需要回答两个问题：该用什么算法？
为什么是 SPFA？
SPFA 是 Bellman-Ford 的队列优化，适合在带权图上求单源最短路/最长路。本题中残量网络没有负环（反向边权值为负，但与正向边构成环的总权为 $0$），因此 SPFA 可以正确收敛。
此外，我们需要的是最长路而非最短路——因为要最大化费用。SPFA 天然支持将松弛条件从 $dist[v] > dist[u] + w$ 改为 $dist[v] < dist[u] + w$，直接求最长路。
SPFA 算法执行流程：
为什么是最小费用最大流？
费用流解决的是“在流量受限的网络中，寻找最优费用的流分配方案”。本题中：
- 节点有容量限制（$b_i$）→ 对应费用流中的边容量
- 配对产生收益（$c_i + c_j$ / 次）→ 对应边的单位费用
- 每对只能配对一次 → 二分图边的容量限制
- 目标是最大化总收益 → 最大费用最大流
这些条件与费用流的建模完全吻合。
最小费用最大流（SPFA 版）执行流程：
算法分析
SPFA 最短路径算法
SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 算法的队列优化版本。其核心思想是：只有当某个节点的最短距离被更新时，才用它去松弛邻居节点。
算法流程：
- 初始化 $dist[s] = 0$，其余 $dist[v] = \infty$（最短路径）或 $-\infty$（最长路径）。
- 将源点 $s$ 加入队列，标记 $inq[s] = \text{true}$。
- 当队列非空时，队首 $u$ 出队，$inq[u] = \text{false}$。遍历 $u$ 的每条出边 $(u, v)$，若残量 $> 0$ 且满足松弛条件（最短路：$dist[v] > dist[u] + w$; 最长路：$dist[v] < dist[u] + w$），则更新 $dist[v]$，若 $v$ 不在队列中则入队。
- 队列为空时算法结束。
正确性： SPFA 本质上是 Bellman-Ford 的优化。Bellman-Ford 每轮遍历所有边，而 SPFA 仅当某个节点的距离被更新时才处理其出边，避免了大量无意义的松弛操作。在随机图上 SPFA 期望时间复杂度为 $O(kE)$（$k \le 2$），但最坏情况仍为 $O(VE)$。
关于 SPFA 的讨论： SPFA 在特定构造数据下会被卡到指数级，因此有“SPFA 已死”的说法。但在竞赛中，对于没有负环且图结构随机的场景，SPFA 通常表现良好。若需严格保证复杂度，可改用 Dijkstra（需配合 Johnson 重标号或 Primal-Dual 框架）。详见 最短路算法。
最小费用最大流
最小费用最大流（Minimum Cost Maximum Flow）问题要求在给定网络中，在达到最大流量的前提下，使总费用最小。其核心思路是：在残量网络上反复寻找费用最小的增广路，沿该路径增广，直到不存在增广路为止。
对于最大费用最大流，只需将边权取反，等价于求最小费用最大流后取反结果；或者直接在残量网络上求最长增广路。
算法流程（SPFA 实现）：
- 在残量网络上以源点为起点运行 SPFA 求最短路（最小费用流）或最长路（最大费用流）。
- 若汇点不可达（或最长路费用 $\le 0$），算法结束。
- 沿最短路/最长路从汇点回溯到源点，确定增广流量 $f$（路径上各边残量的最小值）。
- 沿路径更新残量网络：正向边残量减 $f$，反向边残量加 $f$。
- 累加费用 $f \times dist[T]$，返回步骤 1。
复杂度： 每次 SPFA 为 $O(E)$，增广次数取决于流量上界，总时间复杂度为 $O(k \cdot f \cdot E)$（$k$ 为 SPFA 常数因子，$f$ 为最大流量）。
详见 最小费用最大流。
本题建模
条件转化
“$a_i / a_j$ 或 $a_j / a_i$ 是质数”等价于约分后恰好一个是 $1$，另一个是质数。
证明：设 $g = \gcd(a_i, a_j)$，$x_i = a_i / g$，$x_j = a_j / g$。则 $x_i$ 与 $x_j$ 互质。若 $x_i / x_j$ 或 $x_j / x_i$ 是质数 $p$，由于两者互质，分母必须为 $1$，分子为 $p$。因此恰好一个为 $1$，另一个为质数 $p$。
二分图性质
设 $a$ 的质因数分解（计重数）为 $a = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$，总质因数个数 $cnt(a) = \sum e_i$。
若 $x_i = 1, x_j = p$，则 $a_i = g$，$a_j = g \times p$。$cnt(a_i) = cnt(g)$，$cnt(a_j) = cnt(g) + 1$。两者奇偶性不同。
因此，按 $cnt$ 的奇偶性将节点分为两组，只有不同组的节点间才可能连边。这天然构成一个二分图。
建图
- 源点 $S$ 连向所有 $cnt$ 为奇数的节点 $i$，容量 $b_i$，费用 $0$。
- 所有 $cnt$ 为偶数的节点 $j$ 连向汇点 $T$，容量 $b_j$，费用 $0$。
- 对每对满足配对条件的 $(i, j)$（$i$ 在奇数组，$j$ 在偶数组），从 $i$ 向 $j$ 连边，容量 $\infty$（或足够大的数），费用 $c_i + c_j$（每配对 1 次的单位收益）。
- 在该网络上求最大费用最大流（SPFA 最长路增广）。
边 $(i, j)$ 的容量设为 $\infty$ 是因为实际增广流量受限于 $S \to i$ 和 $j \to T$ 的容量 $b_i$ 和 $b_j$。
建图结构
以样例数据为例，建图如下：
交互模拟器在下面，你可以自己调整参数看匹配过程：
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 305;
const int MAXE = 100000;
const ll INF = 1e18;
// --- 费用流板子 ---
struct Edge {
int to, nxt, cap;
ll cost;
} e[MAXE];
int head[MAXN], ecnt = 1, S, T;
int cnt[MAXN], n;
ll a[MAXN], b[MAXN], c[MAXN];
ll dist[MAXN], pre[MAXN];
bool inq[MAXN];
queue<int> q;
void addEdge(int u, int v, int cap, ll cost) {
e[++ecnt] = {v, head[u], cap, cost};
head[u] = ecnt;
e[++ecnt] = {u, head[v], 0, -cost};
head[v] = ecnt;
}
// SPFA 求最长路（最大费用流）
bool spfa() {
for (int i = 0; i <= T; i++) {
dist[i] = -INF;
pre[i] = 0;
inq[i] = false;
}
dist[S] = 0;
q.push(S);
inq[S] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (e[i].cap > 0 && dist[v] < dist[u] + e[i].cost) {
dist[v] = dist[u] + e[i].cost;
pre[v] = i;
if (!inq[v]) {
inq[v] = true;
q.push(v);
}
}
}
}
return dist[T] > 0; // 只要还有正权路径就继续增广
}
int main() {
scanf("%d", &n);
S = 0, T = n + 1;
// --- 读入 + 质因数分解 ---
for (int i = 1; i <= n; i++) {
scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
// 计算质因数个数（计重数）
ll temp = a[i];
for (int d = 2; d * d <= temp; d++) {
while (temp % d == 0) cnt[i]++, temp /= d;
}
if (temp > 1) cnt[i]++;
}
// --- 源点/汇点连边 ---
for (int i = 1; i <= n; i++) {
if (cnt[i] & 1) // 奇数：左组，源点连过来
addEdge(S, i, (int)b[i], 0);
else // 偶数：右组，连向汇点
addEdge(i, T, (int)b[i], 0);
}
// --- 二分图边 ---
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
ll g = std::gcd(a[i], a[j]);
ll xi = a[i] / g, xj = a[j] / g;
// 检查：一个为1，另一个为质数
bool ok = (xi == 1 && xj > 1) || (xj == 1 && xi > 1);
if (!ok) continue;
// 进一步确认非1的那个是质数
ll p = xi == 1 ? xj : xi;
bool isPrime = true;
for (int d = 2; d * d <= p; d++) {
if (p % d == 0) { isPrime = false; break; }
}
if (!isPrime) continue;
// 奇偶性不同才加边
if ((cnt[i] & 1) == (cnt[j] & 1)) continue;
ll val = c[i] + c[j]; // 单位配对收益
if (cnt[i] & 1)
addEdge(i, j, 1e9, val); // 左→右
else
addEdge(j, i, 1e9, val); // 左→右（保证方向）
}
// --- 增广直到无正权路径 ---
ll ans = 0;
while (spfa()) {
ll flow = 1e9;
for (int i = pre[T]; i; i = pre[e[i ^ 1].to])
flow = min(flow, (ll)e[i].cap);
ans += flow * dist[T];
for (int i = pre[T]; i; i = pre[e[i ^ 1].to])
e[i].cap -= flow, e[i ^ 1].cap += flow;
}
printf("%lld\n", ans);
return 0;
}SPFA 费用流执行流程
交互模拟器
在下方模拟器中修改样例、构建二分图并观察费用流增广过程：
调试记录
实际写代码时踩了几个坑，值得记录：
坑一：质数判断遗漏
第一版代码只检查了“一个为 $1$，另一个大于 $1$”，但没有确认那个大于 $1$ 的数真的是质数。比如 $a_i = 12, a_j = 2$，$g = 2$，$x_i = 6, x_j = 1$。$6$ 不是质数，但第一版会误判为合法边。
修复： 加上质数判断。
坑二：奇偶性检查
第二版发现一个问题：即使 $x_i = 1, x_j = p$（$p$ 是质数），如果 $cnt[i]$ 和 $cnt[j]$ 奇偶性相同，也不应该加边。虽然理论上这种情况不会出现（前面已经证明了），但作为防御性编程，加上检查更安全。
修复： 加 if ((cnt[i] & 1) == (cnt[j] & 1)) continue;。
坑三：增广方向
费用流的增广是找“最长路”（正权最大），而不是最短路径。SPFA 里要用 dist[v] < dist[u] + cost 而不是 dist[v] > dist[u] + cost。一开始搞反了导致 WA。
修复： 确认比较方向。
坑四：__gcd 的兼容性
std::gcd 是 C++17 才有的。如果编译器不支持，可以用 __gcd（GCC 扩展）或者手写。
复杂度分析
- 质因数分解：$O(n \cdot \sqrt{a_i})$
- 建图：$O(n^2)$
- 费用流：SPFA 每次 $O(E)$，增广次数取决于具体数据，本题 $n \le 300$，完全可过
总时间复杂度 $O(n^2 + \text{SPFA} \times E)$，空间 $O(n + E)$。
总结
这道题的关键在于：
- 将数论条件转化为图论结构——质因数个数的奇偶性直接给出二分图划分
- 费用流建模——把“每个节点有容量限制”的匹配问题转化为最大费用最大流
- SPFA 最长路增广——只要还有正权增广路就继续，保证全局最优
这道题的巧妙之处在于，“比值是质数”这个看似复杂的条件，通过质因数分解的视角，变得非常直观。