竞赛图超实用套路——[数据删除]

lnyx 的博客 / 2023-05-03 / 原文

本文为二十一世纪二十年代的最新产物，作者：[数据删除]

想转载这辈子都不用联系我了

本文内容可能过于空虚，建议先扫一遍，然后再分成几个部分每天读一部分，因为这样你才能掌握本文的精髓

竞赛图 是一个很没用的东西，好比数学中的解剖 青蛙 。它也是信奥学习中的不用学习的点，因此把它学好啥用没有。如果你去洛谷等OJ上刷题你会明显感觉到：

竞赛图的题目我都能看得懂题解，但要我自己写却没有思路。这时，解题的套路就凸显出了它的重要性。

套路如浩瀚的题海中的一座灯塔，指引我们解题的方向。 ——[数据删除]

网上其他的文章会叽里咕噜说一堆东西，常见的有

怎么SSH——怎么背下 ip 赋——ctrl cv

可你不妨设想一下，这种套路有实质的作用吗？没有，因为前两步会比第三步还要难写。

一、竞赛图六步走

注意：这 \(6\) 步和所谓的 \(SSH\) 完全不同，后面会讲到。

二、“六步走”的详解

PS：这部分博客会按照六个步骤分为六个小部分，每部分会以一个口诀结束，并会在下方有相应的解释，口诀的作用是方便各位大佬记忆，看我多贴心。

\({\tt}\Huge{[数据删除]大佬太有文采了但是我编不出来口诀，希望有人提供，谢谢}\)

定义：\(n\) 个点，任意两点之间有一条有向边的图

性质：（证明都是瞎写的不保证正确性

竞赛图一定存在一条哈密顿路径

证明：考虑归纳， \(n=1\) 的时候显然成立，现在已经求出 \(n-1\) 个点的竞赛图的哈密顿路径了，发现如果第 \(n\) 个点连出去的边都是指向其他点或者都是指向自己时，一定可以把这个点放到哈密顿路径首或尾，若不满足上面的条件，则一定存在 \(u,v\) 满足有边 \((u,n),(n,v)\) ，直接把 \(n\) 放到 \(u,v\) 中间就好了
竞赛图缩点后成链状

这里的是呈链状，边都是从拓扑序小的连向拓扑序大的

证明：发现缩点后还是一张竞赛图，因为竞赛图一定有哈密顿回路，所以呈链状
竞赛图的每一个强连通分量都存在哈密顿回路

证明：跟哈密顿路径考虑方法很像，归纳，\(n=1\) 的时候显然成立，还是讨论边的指向，如果都是指向其他点或者都是指向自己时，发现这个点一定自己作为一个 \(scc\) ，否则一定可以在他所在的 \(scc\) 的环上找到两点 \(u,v\) 使得边是 \((u,n),(n,v)\) ，这样一定可以加进去
对于一个竞赛图中大小为 \(n\) 的强连通分量，其一定存在大小为 \(\forall len \in [1,i]\) 的简单环

证明：考虑 \(3\) 的证明，我们对于一个强连通分量是一个点一个点加的，每次加之前都会有环，加之后也有环，所以显然是对的
如果 \(u\) 的出度大于 \(v\) 的出度，则 \(u\) 一定可以到达 \(v\)

证明：如果 \(u,v\) 在一个强连通分量里面显然正确，当不在一个强连通分量时考虑缩点后的拓扑序

设 \(u\) 所在的强连通分量是 \(x\)，\(v\) 所在的强连通分量是 \(y\) （注意强连通分量编号是拓扑序倒序

当 \(x>y\) 时，缩点完成链状，显然可以到达

当 \(x<y\) 时，因为缩点完了已经没有环了，所以 \(v\) 连出去的点一定是强连通分量标号小于 \(y\) 的， \(u\) 连出去的点一定是强连通分量标号小于 \(x\) 的，又因为 \(x<y\) ，所以得出 \(u\) 出度小于 \(v\) 出度，寄
存在竞赛图满足每个点出度序列为 \(arr\) 当且仅当将 \(arr\) 排序后，\(\forall k \sum\limits_{i=1}^{k} arr_i \ge {k \choose 2}\) 且 \(\sum\limits_{i=1}^{n} arr_i = {n \choose 2}\) (兰道定理)

证明：必要性显然

充分性考虑构造，先让出边集合 \(A\) 为 \(0,1,2,3…n-1\) ，这显然是可以构造出来的，并且满足上面的条件，现在有一些点不满足，我们换一下边的指向顺序来满足这个条件，设 \(x\) 为第一个不满足 \(A_x=arr_x\) 的地方，\(y\) 为最大的 \(A_y=A_x\) ，\(z\) 为最小的 \(A_z>arr_z\) ，发现 \(A_x < arr_x \le arr_y < A_z\) ，所以必定有一个点 \(p\) 和 \(x,z\) 的关系是边 \((p,x),(z,p)\) 现在只要 \(swap\) 一下两条边指向就可以让 \(A_x+1\rightarrow A_x,A_z-1\rightarrow A_z\) ，发现这个操作一定是可以一直进行的，所以我们就通过不断调整调整出 \(arr\) 来了