目录
定义
任意两点之前有且仅有一条边的有向图。即有向完全图。
赢的点连向输的点，一条边表示一个胜负关系。
性质
一、兰道定理（竞赛图的判定）
比分序列：将每个点的出度从小到大排序的序列。
定理内容：
设s是图G的比分序列。
G是竞赛图的充要条件为：
\(1<=k<=n\\ \sum_{i=1}^ks_i>=C_k^2\)
并且k=n时取等。
实质上是：
对于每个点的出度之和总是大于等于下界，并且最后取等，那么图是竞赛图。
定理证明
必要性显然，任意一个竞赛图都满足兰道定理。
充分性证明：
证明对于一个满足兰道定理的比分序列s对应一个竞赛图。
考虑构造法，现有一个所有点i都像j<i连边的竞赛图，比分序列u为0...n-1。
考虑说明调整一定步数之后u能变成s。
u实质上是比分序列前缀和的下界，每一次都能取等。
现在有
\(1<=k<=n \\ \sum_{i=1}^k s_i>=\sum_{i=1}^ku_i\)
考虑第一步：
在u中找到一个\(u_i<s_i\)的位置i，若找不到说明u，s是同一个序列。
再找到最后一个\(u_i=u_j\)的位置j，然后在j后找到第一个\(u_k>s_k\)的位置k。
现在有：
\(u_k>s_k>=s_j>u_j\\u_k>=u_j+2\)
即一定存在一个位置p，满足p想j连边，k向p连边。
找两个度相差2的点就是为了保证p一定存在。
若度相差1，那么可能k多出来的度连向j，不能说明p一定存在。
现在将\((p,j),(k,p)\)变成\((j,p),(p,k)\)
即\(u_j++,u_k--\)
由于前面都是<或>没有取等，所以对于u和s
\(1<=k<=n \\ \sum_{i=1}^k s_i>=\sum_{i=1}^ku_i\)
仍然成立。
问题形式不变，继续按照这样调整下去，一定能使得u变成s，即s对应一个竞赛图。
调整步数有限的证明：
考虑两个序列的曼哈顿距离：
\(dis(u,s)= \sum_{i=1}^n|u_i-s_i|\)
这个值必为偶数，因为在mod 2意义下可以把绝对值去掉。
而每次曼哈顿距离减小2，所以在\(dis(u,s)/2\)步即可完成调整。
这里选择j与k调整而不i与k调整是因为若直接取i与k调整，虽然仍然存在p，但是调整之后u的比分序列可能不再升序，需要重新排序，而调整j和k就不会出现这种情况。
拓展
1.对于同一个比分序列可能对应本质不同的竞赛图：
比如n=5的点，外面围成一个顺时针的圈，一个内部五角星全部向右，一个全部向左。
2.兰道定理的实质是在一个序列和一定时，可以对于任意两个有关系（边）的位置进行相等量的调整（ai+=v，aj-=v），那么要判定任意一个值的序列是否与序列值的下界形式一样时，只需要判断是否每个前缀和都大于等于下界，以及最后的和与预期相等即可。
这种证明思路比较巧妙，利用构造法不断调整。
由于总量一样，要判定某个状态形式是否合法只需要判定每个前缀是否都大于等于下界。
核心是一条边带来的比分贡献总是一样的，总量不变。
二、竞赛图缩点后拓扑序成链状，拓扑序小的点向所有拓扑序比它大的点连边。
（1）与SCC，拓扑序相关
这个性质很关键，所有与环，SCC相关的问题都可以用这个性质解决。
证明用归纳法：逐个SCC加入，如果连向所有其他SCC，插入头部，如果其他SCC都连向它插入尾部，否则一些拓扑序小的SCC连向它，它连向其余的SCC，那么插入中间某个位置。
不会存在某些拓扑序大的SCC连向它，而它右连向拓扑序更小的SCC，因为这样与SCC的定义矛盾。
推论：
1.根据成链状容易发现当不存在位置i满足以下条件，图为强连通图。
\(\sum_{j=i}^n s_i==(n-i+1)*(i-1)+C_{(n-i+1)}^2\)
其实就是找存不存在某个拓扑序最小的点连向其他点。
2.在同一个SCC中在比分序列上是一个区间，根据比分序列可以完成拓扑排序。（无需建图）
利用拓扑序小的点向所有拓扑序比它大的点连边，从后向前扫，用一个和上面判断SCC本质相同（只是左右端点不同）的式子判定即可。
（2）与三元环和n>=3元环相关
a.竞赛图中若有环一定存在三元环。
证明容易，考虑找到任意一个环，讨论一下顺时针还是逆时针。
以顺时针为例，逐条考虑环中的边。
若为逆向的边，直接有三元环。
若为顺向的边可以看做环少了因这条边存在而绕过的点。
始终不出现逆向的边，最后一条边处构成三元环。
b.竞赛图的k>=3个点的SCC中一定存在[3,k]元环
利用下面的一个SCC内存在哈密顿回路的性质可知存在k元环。
3元环也一定存在。
对于\(3<=i<=k\)元环、
考虑归纳法：
k成立推k-1成立。
若把某个点去掉，存在只存在一个k-1个点的SCC。那么直接证毕，因为存在k-1个点的哈密顿回路。
若不存在，那么根据拓扑序成链状的性质，先忽略掉某个点t，剩下的点有多个SCC，一定成链状，并且存在k-1个点的哈密顿路径。
忽略链尾SCC的任意一个点，然后链尾到t，t到链头即可。如果t不能这样，那么与原来是一个k个点的SCC，矛盾。
三、与哈密顿路径相关的性质（了解即可，哈密顿路径问题不在大纲内）
0.哈密顿路径定义
图中每个点经过一次的路径。
半哈密顿图：存在哈密顿路径的图
哈密顿图：存在哈密顿回路的图。
1.在竞赛图的任意一个SCC中存在哈密顿回路
证明：归纳法，逐个点加入SCC。当前加入的点为u。
若这个点是一个新的SCC，情况同证拓扑序成链状。
若一个点不是新的SCC，那么要么必然存在SCC i和SCC j，（i，j是这个SCC的拓扑序）：
若i<j，那么一定是u向i，j向u。
取最小的i和最大的j，这一段连上的点合成一个SCC，哈密顿回路变成u到i，到j到u。
若i=j，任意找一条i到j的路径，路径上必然存在一条边的两个相邻的结点可以在多经过u的情况下仍然走接下来的路径。
情况类似证明三元环。
2.在竞赛图中存在一条哈密顿路径。
根据每个SCC存在哈密顿回路，一次访问每个SCC，然后按照拓扑序跨SCC访问即可。
例题
计数相关
【集训队作业2018】世界是个动物园
求n个点的强连通竞赛图个数。
解法：
先考虑特殊版问题：（削弱约束）
\(f[i]\) i个点竞赛图个数
\(f[i]=2^{i*(i-1)/2}\)
再考虑原问题：
\(g[i]\) i个点强连通竞赛图个数。
用容斥转移，将图分成两部分，第一个部分是一个SCC，另外一个部分至少是一个SCC，枚举一个j个点的SCC进行转移。
\(g[i]=f[i]-\sum_{j=1}^n g[j]*C_{i}^{i-j}*f[i-j]\)
可以生成函数加速。
用一些数据结构方法可以做到在线。
兰道定理相关
Football Game
题意简述
有n个球队，每两个球队比赛一场，胜者+2分，败者不得分，平局各加一分。
给定一个n个点的得分情况，问是否合法。
解法：兰道定理简单变形（一条边带来的得分贡献为1改成2）
本质上是一条边带来的比分为2的竞赛图，并不关心具体是胜利失败还是平局。
因为无论哪种情况，一条边带来的比分贡献总为2，直接用兰道定理判断即可。
CF850D Tournament Construction
题目简述：
给定一个m个元素的集合a，判断a是否是某个竞赛图的出度集合，若是，则输出点数最少的，任意一个合法的竞赛图。
否则输出不合法。
1<=m<=31,0<=a_i<=30
日期：..4
用时： (思考) + (代码)+（总结）+（复习）
难度：
解法：竞赛图兰道定理（含构造）；dp。
由于m很小，出度值域也很小，并且竞赛图的边数增长速度较快，平方量级。
不难猜想到点数很少。
设一个图有n个点。
边数上界为30*n
而竞赛图的边数\(n*(n-1)/2<=30*n\)
解得\(n<=61\)
根据兰道定理可以在知道点数和各个点的比分序列前缀和判定竞赛图是否合法。
现在需要做的就是对于每个点决策使用出度集合中的哪个出度。
多段决策问题，以每个点划分阶段，对于每个点用出度集合的哪个值作决策，而且数据范围不大，可以用dp解决。
首先，可以看成构造比分序列，这样只需要记录出度集合用到了前j个点，而不需要状压。
也可以从将出度小的用在前面一定不劣（更容易满足兰道定理）角度出发，得到从小到大使用出度集合中的点的结论。
\(f(i,j,k)\) 现在考虑到比分序列的前i个，用了出度集合前j个出度，前i个点比分序列的前缀和为k是否能达到。
根据dp可以直接求出比分序列，根据比分序列构造竞赛图即可。（构造过程就是兰道定理的证明过程）
\(O(61*30*(61*30)+61*(61*30))\)
拓扑序成链状相关（SCC，环相关）
找竞赛图中任意一个三元环
直接找任意一个环即可。然后扫一遍找三元环。具体的：取环上任意一点为s，三元环只可能出现在s，i，i+1的情况。
gym103371K Three Competitions（未实现，需要cdq分治）
题目简述：
给定n个人在三场比赛中的排名，三局两胜，可能存在A直接输B，但是间接赢B的情况。
有q个询问，每次询问a是否能间接或直接赢b。
n,q<=1e5
日期：2.3
用时： (思考) + (代码)+（总结）+（复习）
难度：
解法：三维偏序；竞赛图拓扑序成链状性质；特殊的SCC缩点求法。
容易想到用边来表示两个点之间的关系。
建图，赢的向输的连边。
可以发现，每一对点都存在且只存在一个输赢关系，图是一个每条边有唯一方向的完全图，即竞赛图。
判断是否能赢就是判断两点之间是否有路径。
这里用到一个竞赛图的性质：缩点之后拓扑序成链状。
即存在唯一的拓扑排序，拓扑序小的点向所有拓扑序比它大的点连边。
所以查两个点是否有路径可达，之间查SCC缩点之后的拓扑序关系即可。
根据拓扑序小的的向所有拓扑序比他大的点连边，容易发现只需要知道每个点的出度就可以知道它在哪个SCC，并且拓扑序是多少。
同一个SCC中的点对应出度从大到小排序的一段区间。（由于“拓扑序小的点向所有拓扑序比它大的点连边”这一性质得出。）
具体地，如果对每个点出度从大到小排序，当前从前往后考虑到i，这个SCC是由t点开始的。
当\(\sum_{j=t}^i out_j==C_{i-t+1}^2+(i-t+1)*(n-i)\)时，i是这个SCC所在区间的终点。\([t,i]\)在同一个SCC。
还是由于前面的性质。根据这个可以直接得到这个点在的SCC的拓扑序，拓扑序小的点一定能有到拓扑序大的点的路径，反之一定没有，同一个SCC中一定有路径可达。
求每个点的出度直接三次二维偏序，一次三维偏序就能解决。（学完cdp分治再回来实现）
用到的结论：竞赛图缩点之后为链状。每一个拓扑序小的SCC都向其他所有比它拓扑序大的SCC连边。
结论的证明：
由于完全图，成链状是必然的，不可能出现分叉。
对于一个拓扑序小的SCC，如果它不向后面的SCC连边（其实是所有点），那么由于完全图，后面的点必然向它连边，此时与SCC的定义矛盾。
由此可知，拓扑序小的SCC中的点的出度一定严格大于拓扑序大的SCC的带你的出度，
进一步，同一个SCC一定在一个区间，并且可以算出来端点在哪。
其实就是利用特殊性质拓扑排序的过程。
哈密顿路径相关（了解即可）
POI2017 Turysta
找任意一个点出发的哈密尔顿路径长度。
只考虑第一问，第二问输出哈密顿路径不在大纲范围内。
利用拓扑排序成链状的性质，统计他所在SCC，以及拓扑序比它所在SCC大的SCC的点个数之和即可。
总耗时：251min=4.183h
标签：竞赛,哈密顿,拓扑,SCC,专题,突破,比分,出度 From： https://www.cnblogs.com/xulongkai/p/18007142