$\large\text{Outline}$
- 久远的回忆，时隔一年的回顾。
$\large\text{Algorithm}$
转换题意：
- 求二分图字典序最小的完美匹配。
性质：
- 每个 $i$ 作为左侧点向可能的 $T_i$ 连边，$\text{deg}_i=2$。
- 从后向前匹配增广路可保证字典序最小。
证明：
-
结论一
显然。- $D(x,y)$ 定义式可理解为两点的环上距离，显然只有向前和向后两个方向。
-
结论二
- 很容易发现对于一般化的二分图并不能满足条件。
- 对于左部有 $\forall i,\text{deg}_i=2$ 的二分图而言，我们可以考虑右部点的度数 $\text{deg}_j$。显然 $\sum{\text{deg}_j}=\sum{\text{deg}_i}=2n$。
- 如果 $\text{deg}_j = 1$，由于完美匹配，它所连接的边必须选择，而它所连接左部点 $\text{link}_j$ 的另一条边必不可选。因此可以删除这两条边，对右部点度数总和产生 $-2$ 的贡献。
- 设 $\sum{[\text{deg}_j=1]}=k$，则删边后右部有效点个数为 $(n-k)$，总度数为 $2n-2k=2(n-k)$。因此左右部剩余点的度数均为 $2$。
- 显然新图构成若干偶数长度简单环。此时确定一条边，则其所在环的所有选择均可确定，可以证明贪心策略成立。
做法：
- 即性质 2。
$\large\text{Notes}$
- 没有。