题意
给定(n)个点的竞赛图,有(m)条边的方向是确定的,剩下的边方向不确定,问期望三元环个数
题解
如果一个点(u)有两条已经确定的出边((u,x),(u,y))
那么这组边一定无法构成三元环
所以我们记录每个点的已经确定的出度(d),出度+入度(p)
那么答案就是(ans=C_{3}^{n}-sum_{u=1}^{n}{C_{2}^{d_u}}+ d_u imes frac{n-p_u}{2}+ frac{C_{2}^{n-p_u}}{4})
给定(n)个点的竞赛图,有(m)条边的方向是确定的,剩下的边方向不确定,问期望三元环个数
如果一个点(u)有两条已经确定的出边((u,x),(u,y))
那么这组边一定无法构成三元环
所以我们记录每个点的已经确定的出度(d),出度+入度(p)
那么答案就是(ans=C_{3}^{n}-sum_{u=1}^{n}{C_{2}^{d_u}}+ d_u imes frac{n-p_u}{2}+ frac{C_{2}^{n-p_u}}{4})