给出一个文本文件写有旅行城市信息(travel.txt)，例如下面例子：

8 9 Vancouver Yellowknife Edmonton Calgary Winnipeg Toronto Montreal Halifax Vancouver Edmonton Vancouver Calgary Calgary Winnipeg Winnipeg Toronto Toronto Halifax Montreal Halifax Edmonton Montreal Edmonton Yellowknife Edmonton Calgary

其中8是城市数，9是路线数，在单个单词的行中，给出的是由西至东的城市名，要求旅行路线必须经过最东的城市，就是最下面一个(Halifax)，而且旅行是从最西(最上面一个(Vancouver))的城市出发，然后回到最西的城市，在两个单词的行中，给出的是可以通行的两个城市，求出可以途经最多城市的路线并打印出来。上面只是例子。要求是从文本输入数据，并且文本由用户给出，不需作错误的判断代码，假定题目正确。 针对上面文本的运行结果要如下：

8 7 Vancouver Edmonton Montreal Halifax Toronto Winnipeg Calgary Vancouver

其中8是城市总数，7是途中可以经过的城市数。从最西城市出发(Vancouver)，最后回到最西城市，中间要经过最东城市(Halifax)。如果找不到路线达到题目要求，请输出no solution。 另外不需要作判断错误的代码，就是说假定给出的文本都正确。

最后我给出全部题目，有兴趣的可以做一下，对数据结构有很大帮助。

[此贴子已经被作者于2004-11-20 16:24:02编辑过]

注意，题目中有看不明白的地方可以提问，送出总分是4330，够吸引吧？！ 送分无时间限制，只要做了，不对也有分送，看具体情况，做得对送得多！

其实这题是ACM竞赛题，呵呵，也是我的作业，不要说自己的作业自己想，我也有想，而且我做了一半了，还未想到一些重要部分，请大家开动脑筋帮忙想一下，毕竟我还有数据库作业要做。

[此贴子已经被作者于2004-11-19 21:49:56编辑过]

先占个位置，想想……

我给点我的思路吧，我是这样想的，建一个链表，然后把第一次旅行的路线存进去，然后再建一个链表，中间设一个计算深度的int变量，哪个深就用哪个，删掉浅的那个，然后再建，一直到没有为止，关键是怎样在建立的时候找下一个而不是同一个，这个问题你们还有什么其他思路，可以讨论一下。

好多的积分啊

太累了，想不到，睡了，2楼的思想好像不可行，大家想过另外一些吧。

思路我有一个，用对象化编程，这个题就很好理解了。

首先，每个城市都是一个 object, 每个城市都有其名字，每个城市都有其邻居城市，也就是说可以交通相通的城市，邻居城市的个数是没有限制的。

这样的话，这个class 就看上去是这样的

#include <iostream>

#include <vector>

using namespace std;

typedef vector<City> VCC;

class City

{

private:

char * name;

vector<City> vcNeighborCity;

public:

City();

City(char * cityname, VCC vcNbC); // initialize the object

void set_neighbor(const City & a_city); // add the neighborcity in the neighborcity vector

.......

};

接下来我们便可建立其每层的结构，具体解释如下，

我们从起点城市出发， 那么第一层就为起点城市， 这里具体来讲就是 Vancouver

那么第二层是什么呢？第二层是从 Vancouver 可以到达的城市，这样第二层这里就是 Edmonton 和 Calgary.

再来看第三层，由于Edmonton 有4个邻居城市： Vancouver, Yellowknife, Calgary, Montreal 那么这四个城市作为一个整体属于第三层，他们的起点城市为 Edmonton, 也可以认为这是他们的父城市。 而从Calgary 出发可以有3个到达城市 Vanconver， Edmonton， Winnipeg 这三个城市也作为一个整体处于第三层。

到这里我们便看出我们还需要一个 class

把他命名为 Cityblock ， 在这个class 中定义了属于某个整体群的所有城市，并指出他们的起点城市，以及他们属于的某个层面。这样这个class 看上去就是这样的：

class Cityblock

{

private:

int depth;

City startcity;

vector<City> allcities_in_this_block;

public:

Cityblock();

Cityblock(int d, const City & start, VCC vc_allcities);

void add_city_in_block(const City & a_city);

...

};

在这样的基础上我们便可建立一个模型，他从上到下向左右扩散。

最后由下往上遍历城市，由于每个城市块只有一个起点城市，这样由下往上推不会有重复产生，直到推到最顶端的起点城市，这样我们便有一条路径。为了记录路径，我们还需要一个class , 命名他为 road

class road

{

private:

VCC cities_for_a_road;

public:

void make_road(const City & a_city);

}

...

};

在回推建立 路径的时候，请将块中的城市单元删除，由于用到的是 vector, 删除一个单元很容易，添加单元也将没有限制。

最后将所有建立的路径也存放在一个vector 中。

这样我们对 roadvector 中的所有单元作统计便可得出结论。

// Viel Spass!!!

上面哪个真是高手！