P12544 [UOI 2025] Boys and Girls 题解

zrl123456 · 2026-04-28 19:59:26 · 题解

:::::info[闲话] 神秘做法。
::::: :::::success[Hint 1] 考虑最终选择的边集的形态。
::::: :::::success[Hint 2] 考虑这些形态优的必要条件。
:::::

对应 Hint 1：

自然地，我们先假设选出的某一条边 (u,v)，这个边集是合法的。接下来，不失一般性地设下一条边与其的共点为 v，设这条边为 (v,w)，这两条边构成的边集也合法。接下来分类讨论：

• 当下一条边与第一条边的共点为 u：容易发现这条边一定为 (u,w) 且无法再添加边。
• 当下一条边与第一条边的共点为 v：由于无重边，所以接下来的边一定形如 (v,p),(v,q),(v,k) 等。

总结下我们发现最终图的形态一定是菊花子图或三元环。

对应 Hint 2：

我们发现菊花子图是容易统计进答案的，接下来考虑三元环。

我们发现直接统计过于困难，但是我们考虑到菊花子图可以有一万条边，三元环只有三条，考虑最大值取到三元环时会有更严的要求，三条边的权值也要更大，那么我们考虑借助最大生成树来研究。

• 当所有边都不在最大生成树上时（下文论证建议画图跟随）：
  设三条边为 (u,v),(u,w),(v,w)，根据最大生成树的定义，u,v,w 联通，不失一般性地钦定 u 到 v 有一条不经过 w 的路径，u 到 w 有一条不经过 v 的路径，设 u 到 v 路径上有一条边 (u,p_1)，u 到 w 路径上有一条边 (u,p_2)。
  假设 (u,p_1) 的权值比 (v,w) 小或 (u,p_2) 的权值比 (u,w) 小，我们发现我们均可以通过使用 (v,w) 或 (u,w) 替代 (u,p_1) 或 (u,p_2) 来获得更大的生成树，与生成树的定义矛盾，故 (v,w) 的权值比 (u,p_1) 小（或等于），(u,w) 的权值比 (u,p_2) 小（或等于）。
  这时我们发现 (u,v),(u,p_1),(u,p_2) 一定不比 (u,v),(u,w),(v,w) 劣，那么三条边均不在最大生成树上的情况我们不需要考虑。
• 当只有一条边在最大生成树上时：
  类似上文进行论证，我们也能论证出这种情况不优。
• 当所有边都在最大生成树上时：
  根据最大生成树定义，该情况不存在。

我们得出结论：不劣的三元环一定满足有且仅有两条边在最大生成树上。那么我们直接跑出最大生成树然后枚举非树边考虑它的两端点间的树边和它的贡献，这样我们就做完了这道题。

时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。

code