Problem Description
1967 年, 美国著名的社会学家斯坦利. 米尔格兰姆提出了一个名为 "小世界现象 (small world phenomenon)" 的著名假说, 大意是说, 任何 2 个素不相识的人中间最多只隔着 6 个人, 即只用 6 个人就可以将他们联系在一起, 因此他的理论也被称为 "六度分离" 理论 (six degrees of separation). 虽然米尔格兰姆的理论屡屡应验, 一直也有很多社会学家对其兴趣浓厚, 但是在 30 多年的时间里, 它从来就没有得到过严谨的证明, 只是一种带有传奇色彩的假说而已.
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 组关系, 其他任意两人之间均不相识.
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
思路: 很水的多源对多源最短路问题. 我用的 Dijk();
坑点: 隔 6 个人, 所以最短距离最大为 7 就可以.
- #include<cstdio>
- #include<cstring>
- #define N 105
- #define Inf 0x3f3f3f3f
- using namespace std;
- int G[N][N],mark[N],dis[N];
- int n,m;
- void Getmap(){
- int a,b;
- memset(G,Inf,sizeof(G));
- for(int i=0;i<n;i++)
- G[i][i]=0;
- for(int i=0;i<m;i++){
- scanf("%d%d",&a,&b);
- G[a][b]=G[b][a]=1;
- }
- }
- void Dijk(int s){
- int mini,p;
- memset(mark,0,sizeof(mark));
- for(int i=0;i<n;i++)
- dis[i]=G[s][i];
- for(int k=0;k<n;k++){
- mini=Inf;
- for(int i=0;i<n;i++){
- if(!mark[i]&&dis[i]<mini){
- mini=dis[i];
- p=i;
- }
- }
- mark[p]=1;
- for(int i=0;i<n;i++){
- if(dis[i]>dis[p]+G[p][i])
- dis[i]=dis[p]+G[p][i];
- }
- }
- }
- int main(){
- while(~scanf("%d%d",&n,&m)){
- Getmap();
- int flag=1;
- for(int i=0;i<n;i++){
- Dijk(i);
- for(int j=0;j<n;j++){
- if(dis[j]>7){
- flag=0;
- break;
- }
- }
- if(!flag) break;
- }
- if(flag) printf("Yes\n");
- else printf("No\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2853865.html