【BZOJ 2916】 2916: [Poi1997]Monochromatic Triangles (容斥)

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<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 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
",ans);
31     return 0;
32 }
View Code

2017-04-20 15:57:10

【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/Konjakmoyu/p/6739211.html