ZOJ-1129-Erdos Numbers-白红宇

ZOJ-1129-Erdos Numbers

阅读量：4514 次

发布时间：2019-06-08

本文共 989 字，大约阅读时间需要 3 分钟。

题目大意：

和Erods合作的作者，其Erdos number 是1，没有和Erdos合作的，但是和Erods number是1的作者合作的作者，其Erdos number是2，以此类推。

编程任务：

对给定的一组科学家，计算每位科学家的Erods number。

算法分析：

此题难点主要是对字符串的处理，然后用广度优先搜索求解。

分别对每个作者进行编号，将作者之间的关系构造成邻接矩阵。如果用普通字符串的处理为作者编号，比较麻烦，效率也低，可以利用map()容器。以姓名为key，值为编号

map<string, int > name;

读入数据时，对于每一篇论文，作者编号存放于paper[]中，根据作者编号，构建邻接矩阵。最后用广搜进行求解。

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;struct Editor{ int ID; //作者编号 int Num;//Erdos number 号};vector
           
            data[10000]; //存储邻接矩阵map
            
              name; //作者编号map
             
              ::iterator pos;int author[10000]; //各个作者的Erdos numberstring Erdos = "Erdos,P.";void bfs() //广搜求解{ queue
              
               Q; Editor tmp,now; int i,id,nNum; memset(author,-1,sizeof(author)); tmp.ID = name[Erdos]; tmp.Num = 0; Q.push(tmp); while(!Q.empty()) { now = Q.front(); Q.pop(); id = now.ID; nNum = data[id].size(); for(i=0;i

转载于:https://www.cnblogs.com/pcoda/archive/2012/09/02/2667992.html

你可能感兴趣的文章

Programming Erlang_CHAPTER2_Basic Erlang 学习笔记（2）。