【组合数学】Bzoj2916 [Poi1997]Monochromatic Triangles

Description

空间中有n个点，任意3个点不共线。每两个点用红线或者蓝线连接，如果一个三角形的三边颜色相同，那么称为同色三角形。给你一组数据，告诉你哪些点间有一条红线，计算同色三角形的总数。 n<=1000，m<=250000。  

题解

感觉同色不太好做？

那杂色呢？好做得不得了啊，一个杂色三角形肯定有一对红蓝边

那么我们考虑连接红蓝边的点的贡献

统计了点u连红边条数为t[u]，那么贡献就是t[u]*(n-t[u]-1)

求sigma之后再除二，每个三角形被考虑两次

再用C(n,3)相减就可以了，C(n,3)还可以直接求

于是秒之

 

代码

一鼓作气切掉此题，感觉非常爽

#include<cstdio> const int maxn=1e3+5; int t[maxn]; int n,m,u,v,ans; int main(){ scanf("%d%d",&n,&m); ans=n*(n-1)*(n-2)/3; for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); t[u]++;t[v]++; } for(int i=1;i<=n;i++) ans-=t[i]*(n-t[i]-1); printf("%d\n",ans/2); return 0; }

 

转载于:https://www.cnblogs.com/xkui/p/4540358.html