Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom6月前

12/18
15:33
容斥原理 组合数/lucas

[bzoj 2916] [Poi1997]Monochromatic Triangles

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 空间中有n个点,任意3个点不共线。每两个点用红线或者蓝线连接,如果一个三角形的三边颜色相同,那么称为同色三角形。给你一组数据,计算同色三角形的总数。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行是整数n, 3 <= n <= 1000,点的个数。

第二行是整数m, 0 <= m <= 250000,红线数目。

接下来的m行,每行两个数p和k,1 <= p < k <= n。表示一条红线的两个端点。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一个整数,单色三角形的数目。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

6
9
1 2
2 3
2 5
1 4
1 6
3 4
4 5
5 6
3 6

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

同色三角形数=三角形总数-不同色三角形数

三角形的总数是C(n,3),对于一个点,如果它向两个点连出了异色的边就会有一个不同色三角形,如果它连出了d[i]条红边,就会有(n-1-d[i])条蓝边,同一个异色三角形会被计算2次,所以答案就是C(n,3)-∑d[i]*(n-1-d[i])/2

 

[bzoj 2916] [Poi1997]Monochromatic Triangles