• 搬题人：
  • A：he_____he
  • B：p_b_p_b
  • C：hehezhou
• 组题人：hehezhou
• 题解：hehezhou, p_b_p_b

双向奔赴

题目来源：

• XXI Open Cup named after E.V. Pankratiev. Grand Prix of Korea, Problem C

QOJ 链接：https://qoj.ac/contest/776/problem/3301

一个强连通分量一定可以由如下过程产生：

1. 初始有一个集合 $S$，包含其中的一个点。
2. 每次选择一条链 $u\rightarrow v_1 \rightarrow v_2\rightarrow\cdots\rightarrow v_k\rightarrow w$，其中 $u,w\in S$ ，将 $v_1,v_2,\cdots,v_k$ 加入到 $S$ 中。

对于 $(i,j)$ 的无向边，我们可以默认代价较小的那个方向的有向边一定出现，然后将代价同时减去这个较小值。我们可以状压 dp 这个过程，用 $d_S$ 表示集合变为 $S$ 的最小代价。定义 $f_{S',v,w}$ 表示目前考虑了一条 $u$ 到 $w$ 的链，同时这条链已经走到了 $v$ 点，还剩余 $v$ 到 $w$ 的部分没有完成， 表示 $S'$ 并上这条链中 $u$ 到 $v$ 的部分，此时的最小代价。可以直接枚举链上 $v$ 的下一条边转移。需要注意不能同时包含连接两个点的两个方向的有向边。时间复杂度 $O(2^nn^3)$。

循环移位

题目来源：

• Petrozavodsk Winter 2022. Day 7. Gennady Korotkevich Contest 6, Problem I
• XXII Open Cup named after E.V. Pankratiev, Grand Prix of Gomel, Problem I

QOJ 链接：https://qoj.ac/contest/825/problem/2624

经过打表，发现满足条件或不满足条件的排列都看不出任何性质。

那就只能暴力一点，用 $O(2^{n-1})$ 的时间枚举每个 $i$ 是否有 a[i]<a[1] ，以此获得一个大小关系树。然后再计算有多少个满足条件的排列也同时满足这个大小关系树。

注意到如果当前这个 a[i] 在之前已经被考虑过，那么必然有 a[i]>a[1] 。那么感性理解一下，随着 $i$ 增大，a[i] 从未被考虑过的概率越来越小，从而可能的大小关系树的数量会远小于 $2^n$ 。

写一个带剪枝的 dfs ，发现 $n=42$ 时只有 $\approx 10^9$ 种可能，因此直接暴力打表即可。

和平共处

题目来源：

• RuCode 2020 Division A+B Championship Round, Problem I
• XX Open Cup named after E.V. Pankratiev, Grand Prix of Moscow, Problem I

QOJ 链接：https://qoj.ac/contest/923/problem/4219

题解的做法几乎没有用到平面黑白点的任何性质。

利用一些二分图匹配的性质，不难发现题意等价于求这张二分图的字典序最小的最大匹配，字典序的定义为匹配白点集合的字典序，下面简称字典序最小最大匹配为最优匹配。

我们给出结论：如果能在 $T(n+m)$ 的时间复杂度内计算出左右部分别为 $n,m$ 个点的二分图的最小割以及方案，那么可以在 $T(n+m)\log {n}$ 的时间内计算出左部的最优匹配。这里最小割的定义为：设左部和右部分别为 $L,R$，一个割由左集和右集 $X,Y$ 组成，满足 $X\bigcap Y=\emptyset,X\bigcup Y=L\bigcup R$ 并且 $X\bigcap L$ 和 $Y\bigcap R$ 之间不存在边。割的大小定义为 $X\bigcap R+Y\bigcap L$，令 $X_l=X\bigcap L,X_r=X\bigcap R,(Y_l,Y_r)$ 同理。

具体的做法如下：考虑过程 $F(S_1,S_2,S_3)$ 表示你需要求出左部为 $S_1\bigcup S_2$，右部为 $S_3$ 的最优匹配，并且 $S_2$ 中所有元素小于 $S_1$ 中元素且一定在最优匹配中，答案就是 $F(L,\emptyset,R)$。

将 $S_1$ 按照元素大小划分成大小相同的两部分，元素较小和较大部分分别设为 $X,Y$。求出 $(S_2\bigcup X,S_3)$ 的一个最小割，左集和右集分别设为 $(A_l,A_r),(B_l,B_r)$。

引理 $1$：$(B_l\bigcup Y,B_r)$ 的最优匹配一定包含 $B_l$。

首先 $(B_l,B_r)$ 的最大匹配大小为 $|B_l|$，因此包含 $B_l$，注意到 $Y$ 中所有元素大于 $B_l$ 中元素，由匈牙利算法可得，$(B_l\bigcup Y,B_r)$ 的最优匹配包含 $B_l$。$\square$

引理 $2$：$(X\bigcup S_2,S_3)$ 的最优匹配由 $(A_l,A_r)$ 和 $(B_l,B_r)$ 的最优匹配组成。

两者之间的边只存在于 $A_r$ 和 $B_l$ 之间，这些边不可能成为匹配边，否则这个匹配大小达不到 $|A_r|+|B_l|$。

引理 $3$：$(S_1\bigcup S_2,S_3)$ 的最优匹配由 $(A_l,A_r)$ 和 $(B_l\bigcup Y,B_r)$ 的最优匹配组成。

考虑在 $(X\bigcup S_2,S_3)$ 的最优匹配的基础上，将 $Y$ 中元素逐个加入，模拟找增广路的过程，由于 $Y$ 中元素较大，这样得到的结果就是最优匹配。

每次找到的增广路不可能包含 $A$，因为 $A_l$ 只和 $A_r$ 相连，$A_r$ 所有点均已匹配且匹配点均在 $A_l$，一旦增广路走到 $A$ 就无法出来且找不到未匹配点。因此每个点加入后，$A$ 内部的匹配不会改变。$\square$

对 $(A_l,A_r)$ 的求解直接调用 $F(A_l\bigcap S_1, A_l\bigcap S_2, A_r)$。对 $(B_l\bigcup Y,B_r)$ 的求解调用 $F(Y,B_l,B_r)$。注意到每次递归，每个点恰好会递归至一侧，并且 $S_1$ 的大小减半。递归树仅有 $\log n$ 层，复杂度 $T(n+m)\log n$。

考虑求出一组最小割：这可以贪心解决，具体的，先求匹配，将所有点按照 $x$ 轴排序并枚举，加入黑点时将 $y$ 坐标加入集合，加入白点时找集合中最大的不超过当前白点 $y$ 坐标的黑点，匹配两个点并将黑点从集合中删去，如果找不到则认为匹配不上。然后从所有未匹配的白点开始 bfs，将所有走到的黑点以及他们对应匹配的白点不断加入队列，这可以通过线段树优化建图完成，因此 $T(n)=O(n\log n)$。

总复杂度 $O(n\log^2 n)$。