#3412. 「2020-2021 集训队作业」不讲武德 题解

题目分析

给定一个连通无向图，每条边有两个权值 $a_i$ 和 $b_i$。对于每个 $k = 1, 2, \dots, n-1$，需要选出恰好 $k$ 条边构成森林（无环），使得：

$$\text{cost} = \left(\sum_{i \in S} a_i\right) \times \left(\sum_{i \in S} b_i\right) $$

最小，其中 $S$ 是选中的边集。

---

核心思路

1. 问题转化

这是一个双目标最小生成树问题。对于固定斜率 $\lambda$，定义边权：

$$w_i(\lambda) = a_i + \lambda \cdot b_i$$

按此边权求最小生成树，得到点 $P(\lambda) = (A(\lambda), B(\lambda))$，其中：

$$A(\lambda) = \sum_{i \in MST} a_i, \quad B(\lambda) = \sum_{i \in MST} b_i $$

这些点构成的下凸包包含了所有可能的最优解。

2. 凸包性质

对于目标函数 $f(A, B) = A \times B$，最优解一定在凸包的左下部分。证明如下：

设 $P_1 = (A_1, B_1)$ 和 $P_2 = (A_2, B_2)$ 是凸包上相邻两点，对于 $P = tP_1 + (1-t)P_2$：

$$f(P) = [tA_1 + (1-t)A_2] \times [tB_1 + (1-t)B_2]$$

这是关于 $t$ 的二次函数，最小值在端点处取得。

3. 分治算法

使用分治在凸包上寻找所有 $k$ 对应的最优解：

def solve(l, r):
    # l, r 是凸包上的两个点 (A_l, B_l), (A_r, B_r)
    λ = -(A_r - A_l) / (B_r - B_l)  # 计算斜率
    
    # 用权值 w = a + λ*b 求最小生成树
    mst = kruskal(λ)
    mid = (A_mst, B_mst)
    
    if mid 在 l 和 r 之间:
        solve(l, mid)
        记录 mid 对应的答案
        solve(mid, r)

4. 算法步骤

1. 初始化：找到两个极端点

   • $\lambda \to -\infty$：按 $a_i$ 排序的MST
   • $\lambda \to +\infty$：按 $b_i$ 排序的MST

2. 分治求解：在凸包上递归寻找所有可能的MST

3. 合并答案：对于每个 $k$，取凸包上对应点的最小值

---

复杂度分析

• 凸包上最多 $O(m)$ 个点
• 每次Kruskal算法 $O(m \log n)$
• 总复杂度 $O(m^2 \log n)$
• 满足数据范围 $\sum m^2 \leq 2.5 \times 10^6$

---