题解

思路

先用并查集求出所有连通块大小。选择 $c$ 个连通块并将它们合并需要恰好 $c-1$ 条新道路，因而问题变为：选出总和为幸运数的尽量少的连通块。

做法

子任务 1 枚举连通块子集。子任务 2 对每个连通块做一次 $0/1$ 背包，状态为得到指定顶点总数所需的最少连通块数。

满分算法把大小相同的连通块统计成计数。若大小 $s$ 出现 $c$ 次，就把这 $c$ 份物品按 $1,2,4,\ldots$ 二进制拆分；每一份拆分物品的重量为所含顶点总数，代价为所含连通块数。令 $dp[x]$ 表示凑出恰好 $x$ 个顶点所需的最少连通块数，对每份拆分物品做倒序转移。

最后枚举不超过 $n$ 的所有幸运数 $x$。若所有对应的 $dp[x]$ 都不可达，则输出 $-1$；否则输出最小的 $dp[x]-1$。

正确性说明

并查集得到的连通块正好是初始时无法通过已有公路互相到达的区域。选择 $c$ 个连通块后，用 $c-1$ 条新道路把它们依次连接即可形成一个连通块；反之，每条新道路至多令连通块数量减少一，因此合并这 $c$ 个连通块至少需要 $c-1$ 条道路。

二进制拆分能表示从 $0$ 到 $c$ 的任意取用数量，所以背包枚举了每种大小的连通块所有合法选取数。倒序转移保证每份拆分物品至多使用一次，因此 $dp[x]$ 恰为总大小为 $x$ 时选取的最少连通块数。对所有幸运数取最小值后再减一，得到的就是所需新道路数的最小值。

复杂度

设二进制拆分后物品数为 $B$，时间复杂度为 $O(nB)$，在所有连通块大小之和为 $n$ 的限制下可通过；空间复杂度为 $O(n)$。