ろくどぶんり
6458 ワード
ろくどぶんり
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5411 Accepted Submission(s): 2195
Problem Description
1967年、米国の著名な社会学者スタンリー・ミルグランムは「小世界現象(small world phenomenon)」という有名な仮説を提出した.(six degrees of separation).ミルグラムの理論はしばしば当てはまり、多くの社会学者が興味を持っていたが、30年以上も厳密な証明を得たことがなく、伝奇的な仮説にすぎなかった.
Leleはこの理論にかなり興味を持っていたので、HDUでN人に対して調査を行いました.彼はすでに彼らの間の知り合い関係を得ています.今、「六度分離」が成立したかどうかを検証してください.
Input
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.
各試験群について、第1行は2つの整数N,M(0次にM行があり、行ごとに2つの整数A、B(0<=A、BこのM組の関係を除いて、他の2人は知り合いではありません.
Output
各グループのテストについて、データが「6度分離」理論に合致する場合は、1行に「Yes」を出力し、そうでない場合は「No」を出力します.
Sample Input
8 7 0 1 1 2 2 3 3 4 4 5 5 6 6 7 8 8 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0
Sample Output
Yes Yes
問題解:注意は7より大きい.
コード:
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5411 Accepted Submission(s): 2195
Problem Description
1967年、米国の著名な社会学者スタンリー・ミルグランムは「小世界現象(small world phenomenon)」という有名な仮説を提出した.(six degrees of separation).ミルグラムの理論はしばしば当てはまり、多くの社会学者が興味を持っていたが、30年以上も厳密な証明を得たことがなく、伝奇的な仮説にすぎなかった.
Leleはこの理論にかなり興味を持っていたので、HDUでN人に対して調査を行いました.彼はすでに彼らの間の知り合い関係を得ています.今、「六度分離」が成立したかどうかを検証してください.
Input
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.
各試験群について、第1行は2つの整数N,M(0
Output
各グループのテストについて、データが「6度分離」理論に合致する場合は、1行に「Yes」を出力し、そうでない場合は「No」を出力します.
Sample Input
8 7 0 1 1 2 2 3 3 4 4 5 5 6 6 7 8 8 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0
Sample Output
Yes Yes
問題解:注意は7より大きい.
コード:
1 #include<stdio.h>
2 int map[100][100];
3 int main(){
4 int N,M,flot,p1,p2;
5 while(~scanf("%d%d",&N,&M)){
6 for(int i=0;i<N;++i)for(int j=0;j<N;++j)if(i!=j)map[i][j]=map[j][i]=100;else map[i][j]=0;
7 while(M--){
8 scanf("%d%d",&p1,&p2);
9 map[p1][p2]=map[p2][p1]=1;
10 }
11 for(int i=0;i<N;++i){
12 for(int j=0;j<N;++j){
13 for(int k=0;k<N;++k){
14 map[j][k]=map[j][i]+map[i][k]<map[j][k]?map[j][i]+map[i][k]:map[j][k];
15 }
16 }
17 }flot=1;
18 for(int i=0;i<N;++i){
19 for(int j=0;j<N;++j){
20 if(map[i][j]>7){// 7
21 flot=0;break;
22 }
23 }
24 if(!flot)break;
25 }
26 if(flot)puts("Yes");
27 else puts("No");
28 }
29 return 0;
30 }