new

竞赛图:每两点之间有且仅有一条有向边的图

(chu_i) 出度
(ru_i) 入度

竞赛图三元环计数

补集容斥,总共有(nchoose3)个三元组。
枚举一个点(u)(forall v,win chu_u,(u,v,w))不能构成三元环。
而且显然这样的三元组只会在u被枚举到一次。
所以总的三元环个数为({nchoose3}-sumlimits_{i=1}^n{chu_ichoose2})

竞赛图三元环期望

就是(n)个点的竞赛图给定了(m)条边的方向,剩下的方向都不确定,求期望三元环个数。
这里我们先计算出确定的出度以及入度。然后记(l_i)表示(n-1-chu_i-ru_i)即某个点连出去的未确定方向的边数。
答案为({nchoose3}-sumlimits_{i=1}^n({chu_ichoose2}+frac{chu_il_i}2+frac{l_ichoose2}4))
每个点只把由这个点出发的两条边形成的三元组的情况删掉
考虑两条出边,三种情况,都为已知,一条已知一条不确定,两条不确定,所以要减三个东西

原文地址:https://www.cnblogs.com/Lour688/p/14067780.html