ural 1837. Isenbaev's Number bfs-白红宇

ural 1837. Isenbaev's Number bfs

阅读量：6763 次

发布时间：2019-06-26

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

题目链接：

描述：

Isenbaev是国外的一个大牛。

现在有许多人要参加ACM ICPC。

一共有n个组，每组3个人。同组的3个人都是队友。

大家都想知道自己与大牛的最小距离是多少。

大牛与自己的最小距离当然是0。大牛的队友和大牛的最小距离是1。大牛的队友的队友和大牛的最小距离是2……以此类推。

如果实在和大牛没有关系的只好输出undefined了。

第一行读入n。表示有n个组。1 ≤ n ≤ 100

接下来n行，每行有3个名字，名字之间用空格隔开。每个名字的开头都是大写的。

每行输出一个名字，名字后面空格后输出数字a或者字符串undefined，a代表最小距离。

名字按字典序输出。

思路：

这一题我做的相当纠结，整了好几个小时。其实思路很简单，就是从Isenbaev这个人开始bfs，由于bfs可以记录每个点到起始搜索点的最短距离，正好就是答案。但是要注意没有Ixenbaev的情况，我已开始就栽在这了。

但是有几个问题：1:建图问题。每个点不是 int了，都是string类型，不好建图。后来想了想就用了stl的map，把每个人名和int型映射，int就代表这个节点。先把所有人名插入到map里面，（这时已经按照字典序排列了，map容器的特性）。这样就建好图了。每个人名都有个int编号了，就用邻接矩阵建图再bfs就好了。bfs记录每个节点的dis[] 是多少，可以看看算法导论上这一节讲的挺好的。

2特殊case。有些情况是这组人没有一个人是 Isenbaev，这时候所有人都是undefined.一开始就没考虑到结果runtime error #3.

//g++ 4.7.2 0.031s#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
           //Don't forget this,or failed compile by vc++using namespace std;const int M = 300;bool adj[M][M], vis[M]; //adj[][]邻接矩阵int n, dis[M];void bfs(int start){ int u; queue
          
            q; u = start; dis[u] = 0; q.push(u); vis[u] = 1; while (!q.empty()) { u = q.front(); q.pop(); for (int v = 1; v <= n; ++v) { if (!vis[v] && adj[u][v]) { vis[v] = 1; dis[v] = dis[u] + 1; //记录距离 q.push(v); } } }}int main(){ int casenum; scanf("%d", &casenum); string name[M][4]; std::map
           
             t; for (int i = 1; i <= casenum; ++i) for (int j = 1; j <= 3; ++j) { cin >> name[i][j]; //先把输入存在name[][]里面 t.insert(make_pair(name[i][j], 0)); } int num = 1; std::map
            
             ::iterator it; for (it = t.begin(); it != t.end(); ++it) //给按照字典序排好的人名映射编号作为图的结点 (*it).second = num++; for (int i = 1; i <= casenum; ++i) { int it1 = (*t.find(name[i][1])).second, it2 = (*t.find(name[i][2])).second, //找到这三个点，建立邻接矩阵 it3 = (*t.find(name[i][3])).second; adj[it1][it2] = adj[it2][it3] = adj[it1][it3] = 1; adj[it2][it1] = adj[it3][it2] = adj[it3][it1] = 1; //无向图，一开始忘了这一句害我调试半天 } n = t.size(); //有多少个不同的人 it = t.find("Isenbaev"); if (it == t.end()) //处理没有Isenbaev的特殊情况 { for (it = t.begin(); it != t.end(); ++it) cout << (*it).first << " " << "undefined" << endl; return 0; } bfs((*it).second); for (it = t.begin(); it != t.end(); ++it) { if (dis[(*it).second] == 0 && (*it).first != "Isenbaev") //处理不连通的点，此时它的dis是0，但不是Isenbaev cout << (*it).first << " " << "undefined" << endl; else cout << (*it).first << " " << dis[(*it).second] << endl; } return 0;}

转载地址：http://riseo.baihongyu.com/

你可能感兴趣的文章