【BZOJ 2916】 2916: [Poi1997]Monochromatic Triangles （容斥）-白红宇

【BZOJ 2916】 2916: [Poi1997]Monochromatic Triangles （容斥）

阅读量：5051 次

发布时间：2019-06-12

本文共 1281 字，大约阅读时间需要 4 分钟。

2916: [Poi1997]Monochromatic Triangles

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 310  Solved: 150

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

数据已加强

Source

【分析】

　　三角形只有4种情况。

　　同色：红红红、蓝蓝蓝

　　非同色：红红蓝、红蓝蓝。

　　发现如果找到红-蓝，那么肯定是非同色，不用管第三条边，然后会重复两次算到它。

　　于是答案=全集-非同色。直接枚举连接点就好了。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define LL long long 8 #define Maxn 1010 9 10 int d[1010];11 12 int main()13 {14     int n,m,ans=0;15     scanf("%d%d",&n,&m);16     memset(d,0,sizeof(d));17     for(int i=1;i<=m;i++)18     {19         int x,y;20         scanf("%d%d",&x,&y);21         d[x]++;d[y]++;22     }23     for(int i=1;i<=n;i++)24     {25         int x=n-1-d[i];26         ans-=1LL*x*d[i];27     }28     ans/=2;29     ans+=1LL*n*(n-1)*(n-2)/6;30     printf("%d\n",ans);31     return 0;32 }