Triangle LOVE

时间：2015-08-14 21:33:45 阅读：256 评论：0 收藏：0 [点我收藏+]

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 3574 Accepted Submission(s): 1401

Problem Description

Recently, scientists find that there is love between any of two people. For example, between A and B, if A don’t love B, then B must love A, vice versa. And there is no possibility that two people love each other, what a crazy world!
Now, scientists want to know whether or not there is a “Triangle Love” among N people. “Triangle Love” means that among any three people (A,B and C) , A loves B, B loves C and C loves A.
Your problem is writing a program to read the relationship among N people firstly, and return whether or not there is a “Triangle Love”.

Input

The first line contains a single integer t (1 <= t <= 15), the number of test cases.
For each case, the first line contains one integer N (0 < N <= 2000).
In the next N lines contain the adjacency matrix A of the relationship (without spaces). A_i,j = 1 means i-th people loves j-th people, otherwise A_i,j = 0.
It is guaranteed that the given relationship is a tournament, that is, A_i,i= 0, A_i,j ≠ A_j,i(1<=i, j<=n,i≠j).

Output

For each case, output the case number as shown and then print “Yes”, if there is a “Triangle Love” among these N people, otherwise print “No”.
Take the sample output for more details.

Sample Input

Sample Output

Case #1: Yes
Case #2: No

#include<stdio.h>
#include<string.h>
char p[2001][2001];
int s[2001],m;
void TO(int n)
{
	int flag=0;
	int i,j,k;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		if(s[j]==0)
		break;
		if(j==n)
		{
			flag=1;
			break;
		}
		s[j]=-1;
		for(k=0;k<n;k++)
		if(p[j][k]=='1'&&s[k]!=0)
		s[k]--; 
	}
	printf("Case #%d: ",++m);
	if(flag) printf("Yes\n"); 
	else printf("No\n");
	
}
int main()
{
	int t,n;
	m=0;
	scanf("%d",&t);
	while(t--)
	{
		memset(s,0,sizeof(s));
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			scanf("%s",p[i]);
			for(int j=0;j<n;j++)
			{
				if(p[i][j]=='1')
				s[j]++;
			}
		}
		TO(n);
	}
	return 0;
}

再贴一个代码：

#include<stdio.h>
#include<string.h>
char p[2001][2001];
int s[2001],m;
void TO(int n)
{
	int flag=0,i,j,k,w=1000000,h;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		if(s[j]==0)
		{
			w=j;break;
		}
		else w=1000000;
		if(w==1000000)
		{
			printf("Case #%d: ",++m);
			printf("Yes\n");
			return ;
	     }
		s[w]=-1;
		for(k=0;k<n;k++)
		if(p[w][k]=='1')
		s[k]--; 
	}
	printf("Case #%d: ",++m);
	printf("No\n");
	return ;
}
int main()
{
	int t,n;
	m=0;
	scanf("%d",&t);
	while(t--)
	{
		memset(s,0,sizeof(s));
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			scanf("%s",p[i]);
			for(int j=0;j<n;j++)
			{
				if(p[i][j]=='1')
				s[j]++;
			}
		}
		TO(n);
	}
	return 0;
}

Triangle LOVE

原文：http://blog.csdn.net/l15738519366/article/details/47666355

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)