hdu-1869-六度分离(dijkstra)

简介: hdu-1869-六度分离(dijkstra)


六度分离

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5935    Accepted Submission(s): 2395


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      

 


Author

linle

 


Source

2008杭电集训队选拔赛——热身赛

 


Recommend

lcy   |   We have carefully selected several similar problems for you:   2544  1068  3790  1548  1010

 



题目分析:

这个开始没搞懂怎么判断六度分离  。搜了一下明白了是这样:  就是把有关系的两个人 的距离假设为 1  那么就是判断每一个人与其他人要想产生关系只需走6步

比如说   1->3->4->6->8->2  如果1要和2想产生关系 那么就要 走五步  经过4个人就认识了。要想判断是否是六度分离那么任意一个人到其他所有人的最短距离必须小于7  就是通过六个人就能认识了

#include<cstdio>
#include<algorithm>
#include<cstring>
#define max 0x3f3f3f3f
using namespace std;
int dis[110],cost[110][110],mark[110];
int n,m;
void dijkstra(int s)
{
  memset(mark,0,sizeof(mark));
  memset(dis,max,sizeof(dis));//开始一直错在此处把初始化的位置放错地方了,必须得放在这里,每次查一个人就要初始化
  dis[s]=0;
  while(1)
  {
    int v=-1;
    for(int i=0;i<n;i++)
      if(!mark[i]&&(v==-1||dis[i]<dis[v]))
        v=i;
    if(v==-1)
      break;
    mark[v]=1;
    for(int i=0;i<n;i++)
      dis[i]=min(dis[i],dis[v]+cost[v][i]);
  }
}
int main()
{
  while(~scanf("%d%d",&n,&m))
  {
    memset(cost,max,sizeof(cost));
    while(m--)
    {
      int a,b;
      scanf("%d%d",&a,&b);
      cost[a][b]=cost[b][a]=1;//把有关系的人都标为1
    }
    int flag=1;
    for(int i=0;i<n;i++)
    {
      dijkstra(i);//  查一下每个人到其他任意人的最短距离
        for(int j=0;j<n;j++)
        {
          if(dis[j]>7) //  只要存在一个人到某个人的最短距离大于7,那么就不符合六度分离了  
          {
            flag=0;
            break;
          } 
        }
      if(flag==0)
        break;    
    }
    if(flag)
        printf("Yes\n");
    else
      printf("No\n");
  }
  return 0;
}



目录
相关文章
|
Kubernetes Cloud Native 开发者
基于 K8s 做应用发布的工具选择:Tekton,一颗璀璨的CI/CD新星!
【8月更文挑战第8天】在众多Kubernetes应用发布工具中,阿里巴巴为何青睐Tekton?Tekton“以应用为中心”的设计理念与阿里巴巴的技术哲学相契合,不仅关注代码构建部署,还覆盖应用全生命周期管理,完美融入阿里巴巴业务场景。Tekton提供灵活工作流定义、多平台支持及与Kubernetes生态无缝集成等功能,满足阿里巴巴复杂业务需求的同时赋予开发者更多灵活性。作为CNCF毕业项目,Tekton拥有活跃社区和不断壮大的生态系统,为阿里巴巴技术演进提供坚实基础。综上所述,阿里巴巴选择Tekton是一个深思熟虑且具前瞻性的决策。
370 0
|
11月前
|
存储 分布式计算 NoSQL
MongoDB Map Reduce
10月更文挑战第23天
105 1
|
应用服务中间件 Linux iOS开发
使用 setenv 配置文件管理 Tomcat 的自定义环境变量
【8月更文挑战第29天】通过在Tomcat安装目录的`bin`文件夹下创建`setenv.sh`或`setenv.bat`文件,可以轻松管理Tomcat的自定义环境变量。针对Linux/macOS系统,需编辑`setenv.sh`文件,如`export MY_CUSTOM_VAR=&quot;my custom value&quot;`;而在Windows系统中,则编辑`setenv.bat`,如`set MY_CUSTOM_VAR=my custom value`。
743 1
|
JavaScript Java 关系型数据库
租房管理|基于SprinBoot+vue的租房管理系统(源码+数据库+文档)
租房管理|基于SprinBoot+vue的租房管理系统(源码+数据库+文档)
210 0
|
关系型数据库 MySQL 数据库
Metasploit -- 辅助模块(Auxiliary)
Metasploit -- 辅助模块(Auxiliary)
216 0
|
网络协议
centos8 网卡 Nmcli(是network的简写 Nmcli)配置网络
centos8 网卡 Nmcli(是network的简写 Nmcli)配置网络
463 0
|
项目管理 Windows
软件工程IT项目管理复习之 九:项目人力资源管理
软件工程IT项目管理复习之 九:项目人力资源管理
438 0
|
前端开发 JavaScript 开发者
less详解
拥抱前端开发的未来,掌握Less的魔力!在我们精心撰写的博客文章中,你将发现如何通过学习Less这一强大的CSS预处理器,以更高效、更可维护的方式编写样式代码。无论你是初学者还是经验丰富的开发者,我们的指南将带你逐步了解Less的核心概念和语法。通过实际示例和深入解析,你将从中汲取灵感,提升你的前端技能。加入我们的学习社区,与同行分享知识,一同探索创新、时尚而富有表现力的前端设计世界! 
244 0
|
分布式计算 算法 Hadoop
Hadoop简介、安装与环境变量配置
Hadoop简介、安装与环境变量配置
620 1
|
Web App开发 安全 JavaScript
Electron 进程间通信的实现方案
本文讲解 Electron 应用开发种,如何调用相关 API 或者使用相关模块达到 Electron 跨进程通信。
11450 3