题解

思路

把图缩点为强连通分量。大小为 $k$ 的分量内部恰好贡献 $\binom{k}{2}$ 对互相可达的节点。因此第一问等价于把 $p$ 表示为若干三角数 $\binom{k}{2}$ 之和，并最小化所有 $k$ 的和 $N$。

得到最少节点数 $N$ 后，将所有强连通分量按一个全序单向连边，任意两个不同分量中的节点都恰好贡献一个单向对。全部无序节点对中有 $p$ 对在同一分量，故第二问答案是 $\binom N2-p$。

做法

子任务 1 枚举小节点数下的全部有向边集，用传递闭包统计互相可达对，直接找到最小节点数。

子任务 2 递归枚举三角数分解，用当前节点数剪枝。

满分做法做完全背包。设 $dp_s$ 表示凑出 $s$ 对互相可达节点所需的最少节点数，对每个 $k\ge2$ 使用体积 $\binom{k}{2}$、代价 $k$ 转移。

复杂度

满分算法时间复杂度 $O(p\sqrt p)$，空间复杂度 $O(p)$。