题解：最大化图结构分数的最优构造

问题分析

我们需要在 $n$ 个节点的所有无向连通图中，最大化分数函数：

$$\text{score}(G) = \sum_{i=1}^n \sum_{j=i+1}^n \text{dist}_G(i, j)x_ix_j $$

关键观察是：最优图结构一定是星型图或类似结构，其中高权重的节点应该放在中心位置以减少整体路径长度。

算法思路

1. 问题转化

将原问题转化为节点分配问题：

• 考虑将节点分配到两个集合：中心节点集合和叶子节点集合
• 中心节点之间距离为1，叶子节点到中心节点距离为1，叶子节点之间距离为2
• 目标是最优地分配节点到这两个集合以最大化总分

2. 动态规划设计

使用背包问题的思想进行动态规划：

状态定义：

• g[j] 表示考虑前 $i$ 个节点时，中心节点集合总权重为 $j$ 时的最大分数

状态转移：

• 情况1：将当前节点作为叶子节点
  • 贡献：$(nw - j - a[i]) \times (m - nw + j + a[i])$
• 情况2：将当前节点作为中心节点
  • 贡献：$j \times (m - j)$

其中：

• $m = \sum x_i$：所有权重之和
• $nw$：当前已考虑节点的权重和
• $a[i]$：按权重降序排列的第 $i$ 个节点权重

3. 算法流程

1. 预处理：将节点按权重降序排序
2. 动态规划：逐个考虑节点，更新分配方案
3. 结果提取：遍历所有可能的中心集合权重，取最大值

复杂度分析

• 排序：$O(n \log n)$
• 动态规划：$O(n \cdot m)$，其中 $m = \sum x_i$
• 总复杂度：在约束 $n \leq 300, x_i \leq 2000$ 下可行

算法优势

1. 问题洞察：识别出最优解具有二分结构特性
2. 高效DP：将组合优化问题转化为背包问题
3. 贪心排序：按权重降序处理，优先安排高权重节点
4. 数学简化：通过代数变换简化距离计算

总结

本题的解法展示了如何将复杂的图结构优化问题转化为经典的动态规划问题。核心创新点在于：

• 结构识别：发现最优图具有星型或近似星型的结构
• 数学模型：将距离求和转化为集合权重的乘积形式
• 动态规划转化：使用背包思想解决节点分配问题