首页 > 代码库 > 单色三角形

单色三角形

2024-07-09 06:37:40   222人阅读

Description

 

在空间中给出了n个点。这些点任三点不共线，并且每两个点之间都有一条线相连，每一条线不是红的就是黑的。在这些点和线组成的三角形中，如果一个三角形的三条边的颜色都相同，那么我们就称这个三角形为单色三角形。现给出所有涂红色的线，试求出单色三角形的数目。

Input

 

 

输入文件的第一行有一个整数T，表示下面有T组测试数据。接下来的行是T组测试数据的描述。每一组测试数据的第1行是两个整数n和m，其中整数n表示点数，m是红色边的数目，（0 <= m <= 250000， 3 <= n <= 1000）。接着有m行，每行包含两个整数p，k，表示这条红边的两个顶点，（1 <= p < k <= n）。

两组测试数据之间有一空行，输入直到文件结束。

 

Output

 

输出文件有若干行。对输入文件中的每组测试数据，输出对应的单色三角形的数目。

Sample Input

2 6 9 1 2 2 3 2 5 1 4 1 6 3 4 4 5 5 6 3 6 3 3 1 2 2 3 1 3

Sample Output

2 1
 
思路还是比较简单的，基本就是做一个数组，行代表着点，然后列记录该点所连接的点
再由列检查连接的数量。
#include<stdio.h>#include<string.h>int a[1000][1000];//记录你连的是什么 int c[1000][1000];int b[1000][1000];//记录你连的是什么 int so1(int x1,int y1);int so2(int x1,int y1);int doge1(int x1);int doge2(int x1);void wow1(int x1,int y1);void wow2(int x1,int y1);int main(){//	 FILE *fp=NULL;  //   fp=fopen("文件.txt","r");  	int m,n;//m点数 n红线数	int i;	int number1=0;	int number2=0;	int j;	int x1,y1;	int apple;	scanf("%d",&apple);	int number=0;	while(apple--)	{	 memset(a,0,sizeof(a)); memset(b, 0,sizeof(b)); memset(c, 0,sizeof(c));	number1=0;	number2=0;		//	fscanf(fp, "%d", &m);//	fscanf(fp, "%d", &n);	scanf("%d%d",&m,&n);	for(i=1;i<=n;i++)	{		scanf("%d%d",&x1,&y1);		//fscanf(fp, "%d", &x1);		//fscanf(fp, "%d", &y1);		b[x1][y1]=1;		b[y1][x1]=1;	}//输入 	for(i=1;i<=m;i++)	{		for(j=1;j<=m;j++)		{			if(b[i][j]==1)wow1(i,j);			else if(i!=j)wow2(i,j);			else ;		}		}//输出矩阵 /*	for(i=1;i<=m;i++)	{		for(j=1;j<=m;j++)		{			printf("%d ",a[i][j]);		}		printf("\n");	}	printf("\n");	for(i=1;i<=m;i++)	{		for(j=1;j<=m;j++)		{			printf("%d ",c[i][j]);		}		printf("\n");	}*/	for(i=1;i<=m;i++)	{		number1=number1+doge1(i);	}	for(i=1;i<=m;i++)	{		number2=number2+doge2(i);	}	printf("%d\n",(number1+number2)/3);			}	//fclose(fp);	return 0;}void wow1(int x1,int y1){	int i=1;	while(a[x1][i]!=0)	{		i++;		if(a[x1][i]==y1)		{			return;		}	}	a[x1][i]=y1;}void wow2(int x1,int y1){	int i=1;	while(c[x1][i]!=0)	{		i++;		if(c[x1][i]==y1)		{			return;		}	}	c[x1][i]=y1;}int doge1(int x1){	int i=1;	int j=2;	int number=0;	int apple=i;	while(a[x1][i]!=0)	{		i++;	}	apple=i-1;//	printf("X1=%d\n",x1);//	printf("apple=%d\n",apple);	for(i=1;i<apple;i++)	{		for(j=i+1;j<=apple;j++)		{			if(so1(a[x1][i],a[x1][j]))			{				number++;//				printf("    3 %d\n",x1);			}					}	}	return number;}int doge2(int x1){	int i=1;	int j=2;	int number=0;	int apple=1;	while(c[x1][i]!=0)	{		i++;	}	apple=i-1;//	printf("apple=%d\n",apple);	for(i=1;i<apple;i++)	{		for(j=i+1;j<=apple;j++)		{			if(so2(c[x1][i],c[x1][j]))			{				number++;//				printf("  %d  %d   \n",c[x1][i],c[x1][j]);			}					}	}	return number;}int so1(int x1,int y1){	int i=1;	int number=0;	while(a[x1][i]!=0)	{					if(a[x1][i]==y1)		{//			printf("---1  %d    2  %d   ",x1,y1); 			return 1;		}			i++;	}	return 0;}int so2(int x1,int y1){	int i=1;	int number=0;	while(c[x1][i]!=0)	{				if(c[x1][i]==y1)		{//			printf("---1  %d 通到 2  %d   ",x1,y1); 			return 1;		}		i++;	}	return 0;}

　　


联系
我们