CF1268D - Invertation in Tournament

给定 \(n\) 个点的竞赛图，每次操作可以反转一个点的所有边的方向，问最少操作多少次使得图强连通。\(n\leqslant 2000\)。

考虑一些性质。

引理：对于 \(n\geqslant 4\) 的强连通竞赛图，存在 \(n-1\) 阶子强连通竞赛图。

证明：考虑任意拎出一个点，不妨设为 \(n\)，对删去这个点后剩下的图缩点，再加入 \(n\) 和与其相连的边，考虑删掉 \(n\) 后缩点形成的极大强连通分量数：

• \(1\) 个强连通分量：删去 \(n\) 即可。
• 不少于三个强连通分量：我们设每个强连通分量按拓扑序排列后为 \(a_1\dots a_k\)，由于原图是强连通图，所以一定存在 \(u\in a_1\) 使得 \(n\) 向 \(u\) 连边，存在 \(v\in a_k\) 使得 \(v\) 向 \(n\) 连边。考虑删掉 \(a_2\dots a_{k-1}\) 中的任何一个点后新图依旧强连通。
• \(2\) 个强连通分量：由于 \(n\geqslant 4\)，所以 \(a_1,a_2\) 其中一个大小不小于 \(2\)，删掉大小不小于 \(2\) 的强连通分量中任何一个不为 \(u,v\) 的点即可。

推论：对于 \(n\geqslant 7\) 的竞赛图，最多操作一次使得图强连通。

证明：考虑原图缩点后的强连通分量分别是 \(a_1\dots a_k\)。

• \(k=1\)：原图强连通，不需要操作。
• \(k\geqslant 3\)：取 \(a_2\dots a_{k-1}\) 中的任何一个点 \(t\) 取反，这样对任意 \(x,y\) 总有路径 \(x\rightarrow v\in a_k\rightarrow t\rightarrow u\in a_1\rightarrow y\)。
• \(k=2\)：此时至少一个强连通分量的大小不小于 \(4\)，不妨设为 \(a_1\)，那么根据引理 \(a_1\) 中一定存在一个点 \(u\)，使得删掉 \(u\) 后， \(a_1\) 依旧强连通。那么翻转 \(u\)，存在分别遍历 \(u,a_1\backslash u,a_2,u\) 的哈密顿回路，所以操作后图强连通。

回到本题，根据上面的推论，我们只需要在 \(n\leqslant 6\) 时暴力枚举每个点是否取反，\(n\geqslant 7\) 时枚举每个点是否取反，然后检查是否是强连通图即可，但是检查是否是强连通图不能直接跑 tarjan，这样总复杂度是 \(O(n^3)\)，这里给一个方法：对出度序列 \(d\) 从小到大排序，如果不存在 \(i<n\) 使得 \(d_1+\dots+d_i=\dfrac{i(i+1)}{2}\)，则原图强连通，其正确性比较显然。所以最后复杂度 \(O(n^2\log n)\)，也可以归并做到 \(O(n^2)\)。

uoj176 - 新年的繁荣

给你 \(n\) 个 \(0\) 到 \(2^m−1\) 之间的整数 \(a_1,\dots, a_n\)。令 \(G\) 为一张 \(n\) 个点的无向完全图，其中第 \(i\) 个点到第 \(j\) 个点的边权为 \(a_i \operatorname{and} a_j\)。
求图 \(G\) 的最大生成树边权和。\(n\leqslant 10^5\)，\(m\leqslant 18\)。

有两种做法，都介绍一下。

考虑 Boruvka 算法，我们每一次只需要找每个连通块向外连出去的边权最大的边，对此，我们维护两个数组 \(f(s),g(s)\)，表示所有 \(s\subset t\) 中权值 \(t\) 所在连通块的编号的最小/最大值，对于每个点只需要贪心查询即可。\(f,g\) 可以类似子集和变换求出，只需要把加法改成取 \(\min/\max\) 即可。这样的复杂度是 \(O((n+m2^m)\log n)\)。

考虑 Kruskal 算法，先假设没有权值相同的点， 我们从大到小枚举边权 \(i\)，那么我们需要找到所有 \(x\operatorname{and}y=i\) 的点对 \((x,y)\) 并合并，显然不能暴力做，考虑我们做一个子集和，那么所有候选集合只有 \(i\) 和 \(i\operatorname{or }2^j\)，我们取一个作为主元，把其他的点如果能合并就合并过来（并查集实现），最后把 \(i\) 的子集和设为主元即可。如果有权值相同的点，根据 Kruskal 算法，这个点连出去的权值最大的边复杂度 \(O(m2^m\log n)\)。