六度分离
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1797 Accepted Submission(s): 702
Problem Description
1967年，美国著名的社会学家斯坦利·米尔格兰姆提出了一个名为“小世界现象(small world phenomenon)”的著名假说，大意是说，任何2个素不相识的人中间最多只隔着6个人，即只用6个人就可以将他们联系在一起，因此他的理论也被称为“六度分离”理论(six degrees of separation)。虽然米尔格兰姆的理论屡屡应验，一直也有很多社会学家对其兴趣浓厚，但是在30多年的时间里，它从来就没有得到过严谨的证明，只是一种带有传奇色彩的假说而已。
Lele对这个理论相当有兴趣，于是，他在HDU里对N个人展开了调查。他已经得到了他们之间的相识关系，现在就请你帮他验证一下“六度分离”是否成立吧。
Lele对这个理论相当有兴趣，于是，他在HDU里对N个人展开了调查。他已经得到了他们之间的相识关系，现在就请你帮他验证一下“六度分离”是否成立吧。
Input
本题目包含多组测试，请处理到文件结束。
对于每组测试，第一行包含两个整数N,M(0<N<100,0<M<200),分别代表HDU里的人数（这些人分别编成0~N-1号)，以及他们之间的关系。
接下来有M行，每行两个整数A,B(0<=A,B<N)表示HDU里编号为A和编号B的人互相认识。
除了这M组关系，其他任意两人之间均不相识。
对于每组测试，第一行包含两个整数N,M(0<N<100,0<M<200),分别代表HDU里的人数（这些人分别编成0~N-1号)，以及他们之间的关系。
接下来有M行，每行两个整数A,B(0<=A,B<N)表示HDU里编号为A和编号B的人互相认识。
除了这M组关系，其他任意两人之间均不相识。
Output
对于每组测试，如果数据符合“六度分离”理论就在一行里输出"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
1 //floyd算法 :联通的话赋值为1，一个点到另一点需要小于等于6步，那么便成立。 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int INF = 10; 8 int map[100][100]; 9 10 int main() 11 { 12 int i,j,k,flag; 13 int m,n; 14 while(cin>>n>>m) 15 { 16 for(i=0;i<n;++i) 17 for(j=0;j<n;++j)//由于是无相连通图，矩阵对称，j<i亦可 18 map[i][j]=map[j][i]=INF; 19 while(m--) 20 { 21 cin>>i>>j; 22 map[i][j]=map[j][i]=1; 23 } 24 for(k=0;k<n;++k) 25 for(i=0;i<n;++i) 26 for(j=0;j<n;++j) 27 { 28 if(map[i][k]!=INF&&map[k][j]!=INF&&map[i][j]>map[i][k]+map[k][j]) 29 map[i][j]=map[i][k]+map[k][j]; 30 } 31 flag=1; 32 for(i=0;flag&&i<n;++i) 33 for(j=0;j<n;++j)//由于是无相连通图，矩阵对称，j<i亦可 34 { 35 if(map[i][j]>7) 36 { 37 flag=0; 38 break; 39 } 40 } 41 if(flag) 42 cout<<"Yes"<<endl; 43 else 44 cout<<"No"<<endl; 45 } 46 return 0; 47 }
View Code
1 //wa,因为其他点间默认为0，表示有路径，这是错误的 2 #include <iostream> 3 #include <cstring> 4 using namespace std; 5 6 bool vis[200][200] = {0}; 7 int d[100]; 8 int f[100][100]; 9 int m,n; 10 11 void floyd() 12 { 13 int i,j,k; 14 for(k=0; i<n; k++)//把中间的k写成i了 15 for(i=0; i<n; i++) 16 for(j=0; j<n; j++) 17 { 18 if(f[i][j] < (f[i][k] + f[k][j]))//应该是大于号 19 f[i][j] = f[i][k] + f[k][j] ; 20 } 21 } 22 23 bool check() 24 { 25 int i,j; 26 for(i=0; i<n; i++) 27 for(j=0; j<n; j++) 28 if(f[i][j] > 7)//不能加等号的 29 return false; 30 return true; 31 } 32 33 int main() 34 { 35 int i,j,k,t; 36 while(cin>>n>>m) 37 { 38 if(0 == n) 39 break; 40 if(0 == m) 41 { 42 cout<<"No"<<endl; 43 break; 44 } 45 memset(vis,0,sizeof(vis)); 46 memset(f,0,sizeof(f)); 47 memset(d,0,sizeof(d)); 48 int from,to; 49 for(i=1; i<=m; i++) 50 { 51 cin>>from>>to; 52 f[from][to] = f[from][to] = 1;//两个数组写的一样啦 53 } 54 floyd(); 55 bool flag = check(); 56 if(flag == true) 57 cout<<"Yes"<<endl; 58 else 59 cout<<"No"<<endl; 60 61 } 62 //while(1); 63 return 0; 64 }
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int INF = 100000; 6 int f[100][100]; 7 int m,n; 8 9 void floyd() 10 { 11 int i,j,k; 12 for(k=0; k<n; k++)//原来把中间的k写成i了 13 for(i=0; i<n; i++) 14 for(j=0; j<n; j++) 15 { 16 if(f[i][k]<INF && f[k][j]<INF && (f[i][j]>(f[i][k]+f[k][j])))//不能加f[i][j]<INF ，因为这样的话永远为No 17 f[i][j] = f[i][k] + f[k][j] ; 18 } 19 } 20 21 bool check() 22 { 23 int i,j; 24 for(i=0; i<n; i++) 25 for(j=0; j<n; j++) 26 if(f[i][j] > 7) 27 return false; 28 return true; 29 } 30 31 int main() 32 { 33 int i,j,k,t; 34 while(cin>>n>>m) 35 { 36 //if(0 == n) 37 // break; 38 // if(0 == m) 39 // { 40 // cout<<"No"<<endl; 41 // break; 42 // } 43 for(i=0; i<n; i++) 44 for(j=0; j<n; j++) 45 if(i==j) 46 f[i][i] = 0; 47 else 48 f[i][j] = f[j][i] = INF;//表示无路径，相对于第一版代码改变的地方 49 50 int from,to; 51 for(i=1; i<=m; i++) 52 { 53 cin>>from>>to; 54 f[from][to] = f[to][from] = 1; 55 } 56 floyd(); 57 // for(i=0; i<n; i++) 58 // for(j=0; j<n; j++) 59 // { 60 // cout<<f[i][j]<<" "; 61 // if(j==n-1) 62 // cout<<endl; 63 // } 64 bool flag = check(); 65 if(flag == true) 66 cout<<"Yes"<<endl; 67 else 68 cout<<"No"<<endl; 69 70 } 71 //while(1); 72 return 0; 73 }
