F题：求最佳旅行路线 (Input File:travel.in/Output File:travel.out) (Submit:travel.exe)

　　你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行。从最西的一个城市出发，单方向从西向东经若干城市到达最东一个城市（必须到达最东的城市）；然后再单方向从东向西飞回起点（可途经若干城市）。除起点城市外，任何城市只能访问1次。起点城市被访问2次：出发1次，返回1次。除指定的航线外，不允许乘其它航线，也不允许使用其它交通工具。求解的问题是： 　　给定城市表列及两城市之间的直通航线表列，请找出一条旅行路线，在满足上述限制条件下，使访问的城市数尽可能多。 　　多个不同的输入数据组写在一个名为C:\ION\ITIN.DAT的ASCII文件中，文件中每一数据组的格式说明如下： 　　·数据组的第1行是N和V N 恰巧有可以被访问的城市数，N是正整数，N<100 V 代表下面要列出的直飞航线数，V是正整数 　　·以下N行中每一行是一个城市名，可乘飞机访问这些城市。城市名出现的顺序是：从西向东。也就是说，设i,j代表城市表列中城市出现的顺序，当i>j时，表示城i在城j的东边（这里保证不会有两个城市在同一条经线上）。 　　城市名是一个长度不超过15个字符串，串中的字符可以是字母或阿拉伯数字。 例如：AGR34或BEL4 　　·接下来的V行中，每行有两个城市名，中间用空格隔开，如下所示：city1 city2 表示city1到city2有一条直通航线，从city2到city1也有一条直通航线。 　　·不同的输入数据组之间被空行隔开（参看例子），最后一个数据组之后没有空行。 下面的例子放在文件C：\IOI\ITIN.DAT中：

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 Calgray

5 5 c1 c2 c3 c4 c5 c5 c4 c2 c3 c3 c1 c4 c1 c5 c2

　　假定输入数据完全正确，不必对输入数据进行检查。对于每一组输入数据 ·第1行是输入数据中给出的城市数 　　·第2行是你所建立的旅行路线中所访问的城市总数M 　　·接下来的（M＋1）行是你的旅行路线的城市名，每行写1个城市名。首先是出发城市名，然后按访问顺序列出其它城市名。注意，最后一行（终点城市）的城市名必然是出发城市名。 如题目无解，则输出数据格式为： 　 ·第1行是输入数据中给出的城市数 　　·第2行写：“NO SOLUTION” 上述例子的解如下所示：

ITIN.SOL

8 7 Vancouver Edmonton Montreal Halifax Toronto Winnipeg Calgary Vancouver

5 NO SOLUTION

[此贴子已经被作者于2004-11-28 02:26:00编辑过]

#include<string> #include<iostream> #include<fstream> #include<vector> using namespace std;

void travel(int m1d[],int visited[],int i,int n,vector<int> &store) { store.push_back(i); //当前访问的城市压入向量 visited[i]=1; //访问过的赋1，初始起点除外

int **matrix=new int*[n]; for(int k=0; k<n; k++) matrix[k]=new int[n]; for(k=0; k<n; k++) { for(int l=0; l<n; l++) { matrix[k][l]=m1d[k*n+l]; //一维转二维 //cout<<matrix[k][l]<<" "; } //cout<<endl; }

//判断当前城市是否有与其连通的城市 int pass=0; for(int s=0; s<n; s++) { if(matrix[i][s]!=0 && !visited[s]) pass=1; }

if(pass==0) { int east=0; vector<int>::iterator p; for(p=store.begin(); p!=store.end(); p++) if(*p==n-1) //判断是否到过最东城市 east=1;

if(east==0) { store.pop_back(); //若已经没有去路，不要用此航线 //visited[i]=0; } }

//关键循环，递归算法精华所在 for(int j=0; j<n; j++) { if(matrix[i][j]!=0 && !visited[j]) //若两点连通且未访问过 { for(k=0; k<n; k++) { for(int l=0; l<n; l++) m1d[k*n+l]=matrix[k][l]; //二维转一维 } int east=0; if(j==0) { vector<int>::iterator p; for(p=store.begin(); p!=store.end(); p++) if(*p==n-1) //判断是否到过最东城市 east=1; } if(east==1) { store.push_back(0); break; }

else travel(m1d,visited,j,n,store); }

//if(store.front()!=store.back()) }

//清除临时申请的内存 for(k=0; k<n; k++) delete[] matrix[k]; delete[] matrix; }

void main() { int N,V;

fstream file1; file1.open("E:\\travel.txt"); file1>>N>>V; //读取城市数和航线数 V*=2; //每条航线有两个城市(起点，终点)

string *city=new string[N]; string *route=new string[V];

for(int i=0;i<N;i++) file1>>city[i]; //读取城市名

int start=-1; for(int j=0;j<V;j++) { file1>>route[j]; //读取航线，双数是起点，单数是终点 if(j%2==0&&start!=0) //判断入口起点航班是否存在 start=city[0].compare(route[j]); }

file1.close();

if(start!=0) //若入口起点航班不存在就退出 { cout<<N<<endl; cout<<"NO SOLUTION"<<endl; exit(0); } //用int类型二维数组储存航班路线 int **connect=new int*[N]; for(i=0; i<N; i++) connect[i]=new int[N];

for(i=0; i<N; i++) for(j=0;j<N;j++) connect[i][j]=0;

//读取当前航线的起点和终点的城市名，连通的数组元素就赋1 for(int k=0; k<V; k+=2) { for(i=0; i<N; i++) if(!(route[k].compare(city[i]))) break; for(j=0; j<N; j++) if(!(route[k+1].compare(city[j]))) break;

connect[i][j]=connect[j][i]=1; }

int *c1d=new int[N*N];

//把图输出一次，输出的同时把值传给一维数组 for(i=0; i<N; i++) { for(j=0; j<N; j++) { //cout<<connect[i][j]<<" "; c1d[i*N+j]=connect[i][j]; //二维数组转一维数组 } //cout<<endl; }

//定义一个变量作访问标记 int *visited=new int[N]; for(i=0; i<N; i++) visited[i]=0;

vector<int> store; //定义向量储存结果路径

travel(c1d,visited,0,N,store); //传递一维数组c1d

//按题目要求输出到屏幕 cout<<N<<endl; vector<int>::iterator pointer; for(pointer=store.begin(); pointer!=store.end(); pointer++) cout<<city[*pointer]<<endl;

//清除刚才申请的所有动态数组用到的内存 delete[] visited; for(i=0; i<N; i++) delete[] connect[i]; delete[] connect; delete[] route; delete[] city; }

[attach]1186[/attach]

由于我用文件流输入数据，所以运行代码前请把上面这个文本文件放到E:盘的根目录下。

不知kai看不看得明白我的想法，我建立了一个矩阵，然后两个城市间连通的话以两个城市的数字为下标的元素赋1值，然后设置一个visited数组，当经过一次，visited就赋1值，代表已经经过过，下次遇到1的元素就跳过，但是问题是我达不到我想要的效果。你把运行的结果和原题的结果比较一下，我注释得不清楚的地方可以问我。

最后，如果kai你也答不了我问题，我就放弃不做了，knocker又不会C++，论坛没有人帮得了我了。

[此贴子已经被作者于2004-11-27 23:27:48编辑过]

我看了你的12楼的题，有了这个附加条件就简单了，起点城市可以经过2次，出发和到达，其余城市都只允许1次。
我帮你看看你的程序。

唉，不好意思，为了这题浪费大家这么多宝贵时间，我实在有愧做版主。

问题主要出在函数里面，主要是我没控制好循环和递归同时用，这是一个递归函数在循环中调用自己，直至找到路径为止，但是在判断路径的连接时我没处理好，所以……

不好意思，我要睡了，你也不要太晚睡了，经常这样身体会熬不住的，晚安。

我回来以后，觉得有点累，就睡了一会儿，起来想这个题，解题的思路我有了，问题的关键是如何建立起模型，然后我又想关于City 这个类应该是怎样的。在我思路清楚之后，我想看看你是如何定义City 这个类的。结果发现，你根本没有对象化编程，还是过程化编程。
C++ 是一门非常适合用于模拟的语言，如果我们能用class 抽象描述对象，那么通过对象与对象之间的互相作用，就可为问题建立物理模型。这正是对象化编程优于过程化编程的地方。
如果你有兴趣对象化编程，请你先写出解题流程图，对于流程图中出现的对象，建立相应的class,然后通过对象间的互相作用，问题自然就解决了。
我会写出我的程序给你看的。

live41， 我希望你从本质上转变到 OOP 编程上，而不是在过程化编程中使用一些cin,cout,以及vector。

这个题目昨天在书店的《程序算法设计》（好象是这个名字）上看到过，清华出版的

这句话说到点子上了，他用的编译器、函数是C++，写的却是C程序^_^