下面是题目，属于IOI竞赛93年第4题，答案在第47~48楼，来自kai版主。

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-12-08 21:46:14编辑过]

if(matrix[i][j]!=0&&!visited[j]) //是这样的，我把二维数组传进来，名字改成matrix

matrix是矩阵的意思，就是当矩阵不等于0而且visited数组的当前元素等于0时，就再递归，visited表示城市被访问过了。

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

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

void travel(int *matrix[],int visited[],int i,int n) { cout<<i<<endl; visited[i]=true; for(int j=0; j<n; j++) if(matrix[i][j]!=0&&!visited[j]) travel(matrix,visited,j,n); }

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

//先把图输出，看看正确否 for(i=0; i<N; i++) { for(j=0; j<N; j++) cout<<connect[i][j]<<" "; cout<<endl; }

int *visited=new int[N];

travel(connect,visited,0,N);

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

谢谢kai，呵呵，昨天去了csdn问，解决了动态二维数组的问题，不过还是没行，在搜索和判断最长路径的时候麻烦了。

ACM的题目就是难啊，怪不得以往拿奖的都是外国学校。

我一开始想到用string数组储存方便，就没想到用vector容器，如果把容器和string一起用更方便。vector<string>

不过我没懂 您(admire u so much) 的意思，在两个类，一个是起点+周边，一个是???

外加一个储存结果的类。

不好意思，是我写漏了条件，的确，加一个条件，就是除了第一个城市以外，其余的都只能经过一次！

kai 你有空吗？可以帮我看看我的代码吗？先不要说换另外一种算法，我很想知道我的代码有什么问题，我已经想破头了，可能先入为主了，局外人看一下会好一点。

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编辑过]