Description
给定空间里n个点，其中没有三点共线。每两个点之间都用红色或蓝色线段连接。如果一个三角形的三条边同色，则称这个三角形是单色三角形。给出红色线段的列表，求出单色三角形的总数。
Input
第一行测试数据的总数T。
对于每个测试数据。
第一行为点数n(3<=n<=1000).
第二行为红色线段的总数m(m<=250000).
接下来m行每行两个整数u和v，表示点u和点v之间的线段为红色线段。
Output
输出单色三角形的总数
Sample Input
1
6
9
1 2
2 3
2 5
1 4
1 6
3 4
4 5
5 6
3 6
Sample Output
2
//这题暴力三重循环也能过。。。数据较弱
328ms
1 #include <stdio.h> 2 #include <string.h> 3 4 int n,m; 5 int ans; 6 int bian[1005][1005];//0为蓝,1为红 7 8 int func(int u) 9 { 10 int i,j; 11 int s1,s2,s3; 12 for (i=u+1;i<=n;i++) 13 { 14 if (i==u) continue; 15 s1=bian[u][i]; 16 for (j=i+1;j<=n;j++) 17 { 18 if (j==u) continue; 19 s2=bian[i][j]; 20 if (s2==s1) 21 { 22 s3=bian[j][u]; 23 if (s2==s3) 24 { 25 ans++; 26 //printf("%d %d %d ",u,i,j); 27 } 28 } 29 } 30 } 31 } 32 33 int main() 34 { 35 int T; 36 scanf("%d",&T); 37 while (T--) 38 { 39 scanf("%d",&n); 40 memset(bian,0,sizeof(bian)); 41 scanf("%d",&m); 42 int i; 43 int u,v; 44 for (i=1;i<=m;i++) 45 { 46 scanf("%d%d",&u,&v); 47 bian[u][v]=bian[v][u]=1; 48 } 49 50 ans=0; 51 for (i=1;i<=n;i++) 52 { 53 func(i); 54 } 55 printf("%d ",ans); 56 } 57 return 0; 58 }
//当然，必须上简便方法，方法是这样的，如果是 n 边形，看其中的一个点，如果有a个红边连着它，就有 n-1-a 的蓝边连着它。
a * (a-1-n) 的意思便是由这个点会组成多少不同颜色的三角形，将点遍历一遍，求出有多少不同颜色的三角形，关键在去重，不是除3，而是除2
因为要组成个三角形不但要连接每个点的两条边，还需要一个边，但是只有两种颜色，所以第三边肯定不是红就是蓝，所以每一个不同颜色的三角形被 2 个点重复计算了，所以除2
然后用组合公式 C(n,3) 减去就是答案
40ms
1 #include <stdio.h> 2 #include <string.h> 3 4 int dot[1005]; 5 int n,m; 6 7 int C(int a,int b)// a!/(a-b)!/b! 8 { 9 return n*(n-1)*(n-2)/6; 10 } 11 12 int main() 13 { 14 int T; 15 scanf("%d",&T); 16 while (T--) 17 { 18 memset(dot,0,sizeof(dot)); 19 scanf("%d",&n); 20 scanf("%d",&m); 21 int u,v; 22 for (int i=0;i<m;i++) 23 { 24 scanf("%d%d",&u,&v); 25 dot[u]++; 26 dot[v]++; 27 } 28 int Q=0; 29 for (int i=1;i<=n;i++) 30 Q+=(n-1-dot[i])*dot[i]; 31 32 int ans=C(n,3)-Q/2; 33 printf("%d ",ans); 34 } 35 return 0; 36 }