CF1559D2 Mocha and Diana 贪心神题

Eggybear · 2021-11-04 17:37:50 · 题解

Description

• 给定两个点集完全相同的森林 A , B ,两个图的连边方式不一样
• 在两个图中同时选两个点连边，使 A, B 仍为森林
• 求最大的连边数量及方案

看不懂的，出门左转

Solution

• 分析题目，仅仅需要维护连通性，很显然需要并查集。
• 那么 D1 其实就出来了，暴力枚举 u , v ,看在 A , B 中是否在同一集合中，如果不同在，连边，复杂度 O(n^2\alpha (n))

重点在D2

我们把相连的点视为一个集合

当我们任意选取 u , v 不难发现，一共会有如下几种情况

前三种情况我们都不能连边，只有第四种情况可以连边

如果我们可以控制第四种情况就好了。。。

怎么办呢，于是这题最最关键的一点就出来了

确定一个中心点

比如说，我们设1号点为中心点。此时，其他点依然有四种情况

• 在 A , B 中都与1相连
• 仅在 A 中与1相连
• 仅在 B 中与1相连
• 在 A , B 中都不与1相连

对于第一种情况，不可能连边。如果，我们把所有的第四种情况的点都变成第一种（和1连边），那么除去第一种情况的点，剩下的点要么在 A 中与1同一集合（第二类点），要么在 B 中与1同一集合（第三类点），所以在二类点中选一个 u ,在三类点中选一个 v ，那么 (u,v) 在 A , B 中一定都不是同一集合，我们只要选两类点中找数量少的那一类，和另外一类随意连边就可以了。

还有一个小问题，二三类点怎么找， vector 存吗？

其实根本不需要，只要 for 扫一遍，并查集 find(i)!=find(1) 就行了。

Analyse

这样连完后，任意选取一个点对 (u,v) ，肯定在 A , B 中同时与1在一个集合，不可能再连边，正确性可以保证。

整个过程我们只需要把所有点扫两遍就行了，总时间复杂度 O(n\alpha(n)) 。

Code

这题代码不难，基本上带着说完了

出门右转

Conclusion

这道题想法很新颖，给森林连边，使用的思路也很巧妙，选取中心点连边保证连通性。当一个题目毫无思路的时候，我们是否可以像这题一样特殊化一个点，让问题变简单，这也许是一个新的思路。