AtCoder ABC302 F - Merge Set
2huk
·
·
题解
题目描述
有 N 个集合 S_1,S_2,\dots,S_N，其中 \left| S_i \right| = A_i,\ S_{i, j} \in [1, M]。
每次选择两个满足 \left| S_i \cap S_j \right| \ge 1 的集合 S_i,S_j，将它们删掉并加上一个新集合 S_i \cup S_j。
问最少多少次操作使得存在一个集合 S_i 满足 1,M \in S_i。
-
1\ \le\ N\ \le\ 2\ \times\ 10^5
-
2\ \le\ M\ \le\ 2\ \times\ 10^5
-
1\ \le\ \sum\limits_{i=1}^{N}\ A_i\ \le\ 5\ \times\ 10^5
-
1\ \le\ S_{i,j}\ \le\ M(1\ \le\ i\ \le\ N,1\ \le\ j\ \le\ A_i)
-
S_{i,j}\ \neq\ S_{i,k}(1\ \le\ j\ <\ k\ \le\ A_i)
分析
这道题可以抽象成图论最短路问题。
考虑这样建图：对于每两个集合 S_i 和 S_j，如果有一个元素 k 满足 k \in S_i,k \in S_j，那么就建一条 S_i \longleftrightarrow S_j 的无向边，表示可以将 S_i 和 S_j 集合合并。
那么显然答案就是某一个包含 1 的集合到某一个包含 M 的集合的最短路。
这样的想法是不错的。但是建图时的时间复杂度是 \Theta(N^2)，而这个复杂度是无法接受的。
观察数据范围 1\ \le\ \sum\limits_{i=1}^{N}\ A_i\ \le\ 5\ \times\ 10^5 ，所以我们考虑把集合和点进行联系。
对于一个集合 S_i，把这个集合和所有其中的元素连接无向边，形成一个二分图，那么跑最短路时只需要从 1 点跑到 M 点即可。
为了方便区分，我们把集合重新编号，即将 S_i 编号为 i + M。所以样例数据建出来的图就应该是这个样子：
其中左边是集合中的元素，右边是集合编号。
这时跑最短路就会多了一些本来不存在的边。首先多了一条起点（也就是 1 点）连向某一个集合的边，也多了一条终点（也就是 M 点）连向集合的边。其次对于原来的每条边现在都多了一条从元素指向集合的边，所以最终答案应该为 \dfrac{res - 2}2（res 为从 1 点到 M 点的最短路）。
这样问题就解决了。求最短路可以直接 BFS。
\text{Code}