- Problem Description Recently,
- scientists find that there is love between any of two people.For example,
- between A and B,
- if A dont 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, ij).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 2 5 00100 10000 01001 11101 11000 5 01111 00000 01000 01100 01110 Sample Output Case#1 : Yes Case#2 : No
题解: 题目中给出 A 不爱 B, 那么 B 必须爱 A 判断有没有三角恋关系, 即 A 爱 B,B 爱 C,C 爱 A 其实只要判断有没有环就可以了 (因为只要有环, 并且 A 和 B 之间一定有关系, 那么一定能找到三角环) 注意这题用 scanf 一个一个字符输入会超时...
- #include <stack>
- #include <queue>
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #define FAST_IO ios::sync_with_stdio(false)
- using namespace std;
- const int N=2000+10;
- int t,n,cnt;
- int in[N];
- char s[N][N];
- vector <int> E[N];
- priority_queue <int> Q;
- void toposort(){
- for(int i=1;i<=n;i++) if(!in[i]) Q.push(i);
- while(!Q.empty()){
- int u=Q.top();Q.pop();
- cnt++;
- for(int j=0;j<E[u].size();j++){
- int v=E[u][j];
- in[v]--;
- if(in[v]==0) Q.push(v);
- }
- }
- }
- int main(){
- FAST_IO;
- cin>>t;
- for(int k=1;k<=t;k++){
- cnt=0;
- memset(in,0,sizeof(in));
- for(int i=0;i<N;i++) E[i].clear();
- cin>>n;
- for(int i=1;i<=n;i++){
- E[i].clear();
- for(int j=1;j<=n;j++){
- cin>>s[i][j];
- if(s[i][j]==1){
- E[i].push_back(j);
- in[j]++;
- }
- }
- }
- toposort();
- if(cnt==n) cout<<"Case #"<<k<<": No"<<endl;
- else cout<<"Case #"<<k<<": Yes"<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2502868.html