题目描述

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

 

      

输入

 

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

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

 

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

     

输出

 

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

样例输入

6 91 22 32 51 41 63 44 55 63 6

样例输出

2

 

题解：

　　显然同色三角形和异色三角形的和为所有的三角形，那么可以通过求异色三角形来求同色。

　　对于异色其三条边必然是红—蓝—蓝 或 红—红—蓝，设三个端点为i,j,k,且i<j<k那么对于枚举顺序来说，其中必有一个点连接的两条边都是同色，而另外两都是1红1蓝，也就意味着，当我们枚举每个端点时，其贡献异色为其红蓝边数之积的一半。

　　话说BZOJ这个程序会被卡，迷？

1 #include
       
         2 const int N=1010; 3 inline int read(){ 4     int s=0;char ch=getchar(); 5     while(ch<'0'||ch>'9') ch=getchar(); 6     while(ch>47&&ch<='9')  s=s*10+(ch^48),ch=getchar(); 7     return s; 8 } 9 int n,m;10 int num[N*N];11 int main(){12     n=read(),m=read();13     int tot=n*(n-1)*(n-2)/6;14     for(int i=1,x,y;i<=m;i++){15         x=read(),y=read();16         num[x]++,num[y]++;17     }18     for(int i=1;i<=n;i++)19         tot-=num[i]*(n-num[i]-1)/2;20     printf("%d\n",tot);21 }