Triangle LOVETime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 3603Accepted Submission(s): 1416
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). Ai,j = 1 means i-th people loves j-th people, otherwise Ai,j = 0.It is guaranteed that the given relationship is a tournament, that is, Ai,i= 0, Ai,j ≠ Aj,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
25001001000001001111011100050111100000010000110001110
Sample Output
Case #1: Yes
Case #2: No
输入一个矩阵，如果a[i][j]==1，意思是i喜欢j，问存不存在一个三角恋关系，，既拓扑排序判环，，要深入理解拓扑排序的原理2015,8,14
#include<stdio.h>#include<string.h>#define M 2100char mp[M][M];int du[M];int n,cas;void topo(){int ok=0,i,k;for(int i=1;i<=n;i++){for(k=1;k<=n;k++)if(du[k]==0) //z找到入度为0的点break;if(k==n+1){//如果不存在入度为0的点，那么就是一定存在环 ，就有三角恋ok=1;break;}else{du[k]–;//删除这个点for(int j=1;j<=n;j++){if(mp[k][j]=='1'&&du[j]!=0)du[j]–;}}}if(ok) printf("Case #%d: Yes\n",cas++);else printf("Case #%d: No\n",cas++);}int main(){int i,j,t;cas=1;scanf("%d",&t);while(t–){memset(du,0,sizeof(du));scanf("%d",&n);for(i=1;i<=n;i++){//按照注释的输入会超时//getchar();scanf("%s",mp[i]+1);;for(j=1;j<=n;j++){//scanf("%c",&mp[i][j]);if(mp[i][j]=='1')du[j]++;}}topo();}return 0;}
有人说,幸福是一种人生的感悟，一种个人的体验。
