计数

Time Limit:0MS     Memory Limit:0KB     64bit IO Format:%lld & %llu

Submit     

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 
          
            2 #include 
           
             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\n",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\n",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 
          
            2 #include 
           
             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