其实题目原版是这样的：

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

说是容易，实现起来难啊！我用的是邻接矩阵啊！把动态二维数组的麻烦搞定了，不过就不知道怎么接下去了。

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

//void travel(int m1d[],int visited[],int i,int n);

void travel(int m1d[],int visited[],int i,int n,string city[]) { cout<<city[i]<<endl; visited[i]=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; }

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]; //二维转一维

travel(m1d,visited,j,n,city); } for(k=0; k<n; k++) delete[] matrix[k]; delete[] matrix; }

void main() { int N,V;

//下面打开文件，C++方式打开 fstream file1; file1.open("E:\\travel.txt"); file1>>N>>V; //取到城市数和通道数 V*=2; //一条通道有两个城市

string *city=new string[N]; //动态申请数组，C++方式 string *route=new string[V];

for(int i=0;i<N;i++) file1>>city[i]; //先把单个城市名储存，string数组

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(); //关闭文件，C++方式 if(start!=0) //如果连起点航班都没有就退出，例如Vancouver存在 exit(0); //下面动态创建二维数组，C++方式 int **connect=new int*[N]; for(i=0; i<N; i++) connect[i]=new int[N];

//先给全部元素赋0值 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;

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

//清除刚才申请的内存，包括之前申请的字符串内存，C++方式 for(i=0; i<N; i++) delete[] connect[i]; delete[] connect; delete[] route; delete[] city; }

楼上的代码是解决了动态二维数组传递参数问题的，最后的关键步骤是：

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]; //二维转一维

travel(m1d,visited,j,n,city); }

怎么处理这个循环使得代码找到最长的路径。

再次说明，这是ACM大赛的，题目，原来是英文的，可能老师们把翻译成中文。

#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) store.pop_back(); //若已经没有去路，不要用此航线

//判断整条航线能否回到入口城市 static int end=0; if(i==0) end=1;

//关键循环，递归算法精华所在 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]; //二维转一维

//关键是这里，加一个判断，怎么加，晕~~~

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

//若最后不能回到入口城市，退出 if(end==0) { cout<<"No Solution"<<endl; exit(0); } }

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; }

[此贴子已经被作者于2004-11-24 00:50:46编辑过]