cmd 的图论练习题（近期总结 2024.3.11）

AGC010E Rearranging

link

题意：一个序列 \(a_{1...n}\)，两个人游戏。先手打乱这个序列，然后后手可以多次选择一对相邻的互质的数交换。先手希望最终序列字典序尽量小，后手则相反。两人都绝顶聪明，求最终序列。

\(1\le n\le 2000,\space 1\le a_i\le 10^8\)

考虑不互质的两个数 \(a_i,a_j\)，他们的相对顺序不会改变。可以发现，在确定所有数对的相对顺序情况下，后手可以任意操作。

在 \(i,j\) 之间连一条边，那么先手相当于给这些边定向成一个 DAG，然后后手给这个 DAG 找个字典序最大的拓扑序列。

因此现在要求的是：给一个图定向成 DAG，使得字典序最小的拓扑序最大。

可以先加一个超级源点，方便处理。

考虑 dfs。当前搜到了 \(u\)，考虑所有连边，如果 \(v\) 没搜过则按 \(u\to v\) 的方向定向，否则 \(v\to u\)。我们先从大的点搜，如果可以连到小的话最好，否则也不亏。

最后一遍拓扑排序求最大字典序的拓扑序即可。记录

AGC038F Two Permutations

link

题意：两个 \(1\sim n\) 的排列 \(p_{1...n},q_{1...n}\)，你需要确定另外两个排列 \(a,b\)，满足 \(\forall i\in [1,n]\) 都有：

• \(a_i=i\) 或 \(a_i=p_i\)

• \(b_i=i\) 或 \(b_i=q_i\)

最大化 \(\sum\limits_{i=1}^n [a_i \not = b_i]\) 的个数，输出这个值。

\(1\le n\le 10^5\)

考虑求最小的 \(\sum\limits_{i=1}^n [a_i=b_i]\)。

对于 \(p\) 的每个环，对应的 \(a\) 要么全是 \(a_i=i\)，要么全是 \(a_i=p_i\)，\(q\) 同理。

那么相当于我们为 \(p\) 和 \(q\) 都选择若干个环，然后对于每个 \(i\) 分类讨论：

• \(a_i=b_i=i\)：此时贡献恒为 \(1\)

• \(a_i\not=i,b_i=i\)：当选择 \(p_i\) 所在环时贡献 \(1\)

• \(a_i=i,b_i\not=i\)：当选择 \(q_i\) 所在环时贡献 \(1\)

• \(a_i\not=i,b_i\not=i,a_i\not=b_i\)：当同时选择 \(p_i,q_i\) 所在环时贡献 \(1\)

• \(a_i\not=i,b_i\not=i,a_i=b_i\)：当同时选择或同时不选 \(p_i,q_i\) 所在环时贡献 \(1\)

考虑 \(p,q\) 环之间的“选、不选产生贡献”的问题，启发我们使用最小割。

（下面用 \(p,q\) 分别表示 \(p_i,q_i\) 所在环）考虑选择 \(p\) 则他与 \(S\) 连通，选择 \(q\) 则他与 \(T\) 连通。具体的：

• \(a_i=b_i=i\)：不用管

• \(a_i\not=i,b_i=i\)：连边 \(p\to T\)

• \(a_i=i,b_i\not=i\)：连边 \(S\to q\)

• \(a_i\not=i,b_i\not=i,a_i\not=b_i\)：连边 \(p\to q\)

• \(a_i\not=i,b_i\not=i,a_i\not=b_i\)：连边 \(p\to q\) 和 \(q\to p\)

时间复杂度 \(O(n\sqrt n)\)。

AGC008E Next or Nextnext

link

题意：给出 \(n,a_{1...n}\)，其中 \(1\le a_i\le n\)。求有多少个 \(1\sim n\) 的排列 \(p\)，满足对于 \(\forall i\in[1,n]\) 都有 \(a_i=p_i\) 或 \(a_i=p_{p_i}\)

\(1\le n\le 10^5\)

考虑连边 \(i\to a_i\)，这是内向基环树森林，对于每个基环树分别求解。

先找出当前环。我们要构造 \(p\)，环上点一定是错杂的排列在 \(p\) 的环上。

（红色是基环树的环上点）

不难发现，如果一个环上点与非环上点的连边数量 \(>1\)，一定无解。

进一步的，如果存在一个点（可以不在环上），他和非环上点的连边数量 \(>1\)，无解。

考虑判完之后基环树长这样：

即每个环上点都可能带着一条链。

考虑一点环上点带着一个环外点，这个环外点可以塞进该环上点和前一个环上点的缝隙中。如果前一个点没有带着链，还可以塞入前一个的缝隙。

如果带着一条 \(s\) 个的链，考虑前面有 \(r\) 个缝隙：

• \(s>r\)：无解

• \(s=r\)：方案数为 \(1\)

• \(s>r\)：方案数为 \(2\)

这样就可以做了。

但是还要判断所有点都不带链的情况，稍微手玩一下会发现一个大小为 \(S\) 的偶环可以合并成大小为 \(2S\) 的环，方案数为 \(S\)。

一个长度 \(S\) 大于 \(1\) 的奇环可以让每个点都往后跳两步，操作后还是一个环，方案数为 \(2\)。

把单独的环分出来，按大小分类，枚举多少个环合并，随便乘一下。

时间 \(O(n)\)。记录