【学习笔记】竞赛图

学习笔记, 竞赛图

竞赛图(tournament)：有 $\binom{n}{2}$ 条边的有向图

性质：

  • 竞赛图强连通缩点后的 DAG 是一条链
  • 竞赛图的强连通块存在一条哈密顿回路
  • 竞赛图存在一条哈密顿路径
  • 竞赛图 $size > 1$ 的强连通块中，大小为 $[3, size]$ 的简单环均存在
  • 兰道定理（竞赛图判定定理）：定义一个竞赛图的比分序列是把竞赛图每个点的出度从小到大排列得到的序列。一个长度为 $n$ 的序列 $s_1 \leq s_2 \leq s_3 \leq … \leq s_n$ 是合法比分序列当且仅当 $\forall i \in [1, n], \sum\limits_{j = 1}^i s_j \geq \binom{i}{2}$，且在 $i = n$ 时取等号，证明 非常巧妙！

计数：

  • $n$ 阶竞赛图个数显然就是 $h_n = 2^{\binom{n}{2}}$ 啦
  • 强连通 $n$ 阶竞赛图个数为 $f_n = h_n - \sum\limits_{i = 1}^{n - 1} f_i \binom{n}{i} h_{n - i}$，就枚举一个 SCC 连的都是出边。

  • 生成函数加速：
    令 $f_0 = 0$

    有：$h_n = \sum\limits_{i = 0}^n \binom{n}{i} f_i h_{n - i} + [n == 0]$

    $H = FH + 1 \Rightarrow F = 1 - H^{-1}$

世界是个动物园

1
2
3
4
5
官方题解:

由于这是竞赛图，不难证明联盟即强连通分量，并且缩完强连通分量之后必然是一条链，前往后连有向边。考虑加入点x之后会发生啥，大概就是找到这条链上第一个有从x出发的边的点和最后一个向x连边的点，把链上这一段删掉，把x插进去代替这一段。我们只要维护一个动态标号，然后把x放在这一段前一个元素里面那一段的后面就好了（记一下每一段的结尾）。

如果你这个用替罪羊或者treap搞一个double出来，区间min max就只要线段树维护就好了。如果你像我一样蠢拿了个splay强行cmp，那么强行rmq复杂度也是对的（两个log在n上），然后你就MLE了（

这个“前往后连”不太准确，缩完是一条链，我们要找区间编号最小的有来自 $x$ 的边的 scc $L$，和编号最大的有去 $x$ 的边的 scc $R$，$[L, R]$ 这一段所有 scc 被缩为一个 scc。替罪羊或者 treap 动态维护编号（其实不用真的删除，搞一个并查集，将 fa 指向 $x$，把 $x$ 插到 $L$ 的位置就好了），线段树查询区间 min、max。用 double 是为了方便创造键值。

$Code$