AGC029F Construction of a tree

pufanyi

题解

发布于：Feb 23, 2020

题意大概就是给你 $n-1$ 个点集，全集是 $\{1,2,\dots, n\}$，现在要从每个点点集中抽出两个点来连边，最终形成一棵树。让你输出方案或判断无解。$n$ 有 $10^5$，所有集合大小之和不超过 $2\times 10^5$。

考虑构造，儿子向父亲连边。也就是说，每个集合最后都是儿子 $\to$ 父亲的一条边，那么我们可以随便选一个点作为跟，其余点肯定对应一个集合，表示这个集合所对应的边，一端是他，另一端是他父亲。其实也就是一个匹配，左边是除了根节点以外的所有点，右边是所有点集。点与点集有边当且仅当这个点在点集中出现。

显然地，如果这个匹配无解那么最终肯定无解，因为根本找不到一个完美的儿子 $\to$ 父亲的映射。找到匹配之后我们把根加上去，跟前面的连法一样。如果连上之后这张图仍然不连通，那么显然无解，因为两个独立的连通块显然没有生成树。

那如果上面的判掉之后是否就一定有解了呢？我们考虑构造解。我们从根节点开始 bfs，我们考虑根节点所有连出去的集合，这些集合的匹配点的父亲都定作是这个根，然后这样递归下去。不难发现，这样做是肯定有解的。

考虑复杂度，边数 $m$ 是集合的总大小，用 Dinic 做二分图匹配，复杂度 $\mathcal{O}(m\sqrt{n})$，之后的构造解复杂度 $\mathcal{O}(m)$，所以总复杂度 $\mathcal{O}(m\sqrt{n})$。

代码

更新于：Jul 2, 2023

网络流

AtCoder