#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) { cout<<i<<endl; visited[i]=true;

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 j=0; j<n; j++) matrix[k][j]=m1d[k+j]; //一维转二维

for(int j=0; j<n; j++) if(matrix[i][j]!=0&&!visited[j]) { for(k=0; k<n; k++) for(j=0; j<n; j++) m1d[k+j]=matrix[k][j]; //二维转一维 travel(m1d,visited,j,n); } 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+j]=connect[i][j]; //二维转一维 } cout<<endl; }

int *visited=new int[N];

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

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

楼上的代码是仍然未解决，kai，你的算法太难，我没心机想对不起……

struct abc { char form[20]; char to[20];}//存储所有的相通的城市数据

char ABC[n];//所有的城市名，从东至西（好象是吧？）

fun()//函数1 从abc中检测一个城市有没有通向下一个城市，有返回下一个城市名,无则返回0

fun1()//入饯，建一个饯,fun()返回的城市进饯，如果不是第一个城市,则以这个城市调fun(),取下一个,如果，fun()返回0,调fun2()将此城市出饯，回到上一个，查看是否还有其它路径

fun2()//出饯，

如果，要取得最佳路径，则另建一个饯2，当得到一个答案，就存入饯2,再得一个，与饯2比较，最好的存入饯2，这样饯2的答案就是最好的

主要思路，就是这样，内容自己补充吧。

其实题目原版是这样的：

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

这是一个图的问题，

本质是求一个最大的环——并且这个环必须包含最东和最西的城市。

储存结结构我觉得以邻接表为佳，

从起点开始对图进行DFS——深度优先搜索，并用一个栈visit[N]对路径进行储存，

注意当回朔同时也应该让相应的结点出栈

如果在遍历结点A时有起点为A的邻接点，且最东的城市已经在路径中，

那visit[N]中存的就是一个满足要求的路径，路径的长度就是栈顶的下标值。

再用另外一个栈存最优解就可以了。

[此贴子已经被作者于2004-11-22 16:46:30编辑过]

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

参看离散数学的图论。用无向网来实现：网络接点表示城市，所有边为1（用于解决这个问题）。这个问题可以转化为求从最西城市到最东城市的最长路径和次长路径，并记录路径上的结点。这两个路径上的结点之和就为问题所求。具体实现可以用修改迪杰斯特拉算法或者修改弗洛伊德算法实现。有时间我一定会写出来给大家see。

邻接表实现起来还是比较容易的啊，只要几个链表操作函数就可以了，

而且在算法的实现上比矩阵简单些

#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大赛的，题目，原来是英文的，可能老师们把翻译成中文。