求最佳旅行路线(IOI题)

我只在乎你

下面是题目，属于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

我是哈密瓜耶

// I have tried your program, the if statement maybe has some logic error, I don't know what do you want.
// please think it over once more
#include<iostream> #include<cstdlib> using namespace std;
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]) // what do you want here??? travel(matrix,visited,j,n); }
int main() { // 2D-Array is extended from 1D-Array const int N_rows = 3; const int N_cols = 3; const int N = 3; int i = 0; int j = 0; int **connect=new int*[N_rows]; for(i=0; i<N_rows; i++) connect[i]=new int[N_cols]; // initialize all value with 0 for(i=0; i<N_rows; i++) { for(j=0;j<N_cols;j++) { connect[i][j]=0; } } int * visited=new int[N]; travel(connect,visited,0,N); //invoke the function
// to release memory for( i = 0; i< N_rows; i++) delete [] connect[i];
delete [] connect; delete [] visited;
system("pause"); return 0; }

成熟之惑

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

┗白觀喑﹖

// 先将最新写的代码贴出来，还没完全写完，在C 板块写了我的算法，大家却不能理解
// 我把代码写的具体了一些，在程序中设置了一个 vector 用于存放单一的 City Object ，每个City Object 拥有
// 两个个性：其名字，另外其邻居城市，其邻居城市也存放于一个 city vector 中。
// 目前程序一切正常。作为测试，将每个城市的邻居城市打印出来，完全正确。
// 接下来是由上至下建立 城市快，每个城市块只有一个起点城市。
// 从一个城市块的城市可以继续往下发展，直到出现这样的局面，即 V->......->...->H->....->....->V
// 也就是说从起点城市又回到了起点城市，当中只经过一次 H
// 这样我们便认为这条支路发展到了尽头。
// 我们必须有能力能够判断，是否某一条支路处于死循环，也就是说从 V 经过一些路径又回到了 V，
// 但永远不经过 H，如果这样则此题无解，这种可能性是存在的。
// 如果所有支路都最终完成，即从 V 出发，一次经过 H 又回到 V ，那么 我们 对所有 Road Object 作统计，
// 那条出现城市数最多的城市便是我们要求的解。
// 另外，我个人认为，动态开辟 2 维数组是一种很丑陋的代码，我个人不会使用。
// 建议使用 class 来模拟 2D Array，并使用 vector
// new 只有在实在不得已的情况下才使用。
// 以下是代码：
// header file: travel.h
#include <iostream> #include <vector> #include <string> #include <cstdlib> using namespace std;
class City; typedef vector<City> VCC;
class City { private: string name; VCC vcNeighborCity; public: City(); City(const string cityname); // initialize the object string get_name(); VCC get_vcinfo(); void set_neighbor(const City & a_city); // add the neighborcity in the neighborcity vector //....... };
class Cityblock { private: int depth; City startcity; VCC 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 { private: VCC cities_for_a_road; public: void make_road(const City & a_city); };
// city.cpp
#include <iostream> #include <string> #include <vector> #include <cstdlib> using namespace std;
#include "travel.h"
City::City() { name = " "; }
City::City(const string cityname) { name = cityname; }
string City::get_name() { return name; }
void City::set_neighbor(const City & a_city) { vcNeighborCity.push_back(a_city); }
VCC City::get_vcinfo() { return vcNeighborCity; }
// cityblock.cpp
#include <iostream> #include <string> #include <vector> #include <cstdlib> using namespace std;
#include "travel.h"
Cityblock::Cityblock(){}
Cityblock::Cityblock(int d, const City & start, VCC vc_allcities) { depth = d; startcity = start; allcities_in_this_block = vc_allcities; }
void Cityblock::add_city_in_block(const City & a_city) { allcities_in_this_block.push_back(a_city); }
// road.cpp
#include <iostream> #include <string> #include <vector> #include <cstdlib> using namespace std;
#include "travel.h"
void Road::make_road(const City & a_city) { cities_for_a_road.push_back(a_city); }
// travel.cpp
#include <iostream> #include<fstream> #include <string> #include <vector> #include <cstdlib> using namespace std;
#include "travel.h"
int main() { int N,V; //????′ò?a???t￡?C++·?ê?′ò?a fstream file1; file1.open("travel.txt"); file1>>N>>V; //è?μ?3?êDêyoíí¨μàêy string city;
VCC vc_cities; for(int i=0;i<N;i++) { file1>>city; //?è°?μ￥??3?êD??′￠′?￡?stringêy×é vc_cities.push_back(City(city)); // set all cities in a city container } string city1, city2; for(int j=0;j<V;j++) { file1>>city1>>city2; int find = 0;
// check all cities in container, wenn we find one then set him a neighborcity if(city1 != city2) { for(int k = 0; k<vc_cities.size() && find<2; k++) { if(vc_cities.at(k).get_name() == city1) { find++; vc_cities.at(k).set_neighbor(City(city2)); } else if(vc_cities.at(k).get_name() == city2) { find++; vc_cities.at(k).set_neighbor(City(city1)); } } } } file1.close(); //1?±????t￡?C++·?ê? // till now, we have all cities in container, and we have also // set the neighborcity for every city in container.
// just to check for(int a = 0; a<vc_cities.size(); a++) { VCC temp = vc_cities[a].get_vcinfo(); for(int b = 0; b<temp.size(); b++) { cout<<temp[b].get_name()<<" "; } cout<<endl; } // code will be continued; // cityblock will be created // for this problem, // depth 0 just a city V // depth 1 we have 1 cityblock : (E,C) with startcity V // depth 2 we have 2 cityblock : (V, M, Y, C) with startcity E // and (V, W, E) with startcity C // depth 3 we have 7 cityblock : (E, C) with startcity V // (H, E) with startcity M // (E) with startcity Y // (V, W, E) with startcity C // (E,C) with startcity V // (C,T) with startcity W // (V, M, Y, C) with startcity E // depth 4 we have 16 cityblock : ... // e.t.c // return 0; }
// 程序还没完全完成，另外局部代码还将改动

追梦人︶ㄣ

谢谢kai，呵呵，昨天去了csdn问，解决了动态二维数组的问题，不过还是没行，在搜索和判断最长路径的时候麻烦了。
ACM的题目就是难啊，怪不得以往拿奖的都是外国学校。

欧阳风

我一开始想到用string数组储存方便，就没想到用vector容器，如果把容器和string一起用更方便。vector<string>
不过我没懂 您(admire u so much) 的意思，在两个类，一个是起点+周边，一个是???
外加一个储存结果的类。

㊣旗舰卍

我仔细地想这道题，觉得题目出的不严谨，它因该还有一个附加条件，即在有限的步数内来经过城市。我们来看下面一个简单的例子：我将那个最西面的城市称为起点城市 S， 那个最东面的城市称为拐点城市 T（TunningCity），如果只有两座城市，即 S 和 T。 那么他们之间必须有连接，路径为 S-T-S 如果有三座城市，那个中间的城市我称它为 M
我们现在来看一个很有趣的事情，假设 S 与 M 有连接， S 与 T 有连接， 而 M 与 T 之间没有连接那么按照我的算法， S 有 邻居城市 M，T M 有 邻居城市 S T 有 邻居城市 S S 作为最初的起点城市， // 第一层那么我们在第一个层面形成了一个 Cityblock,它包含两座城市 M，T // 第二层由 M 出发形成了下一个层面（第二层）的 Cityblock,其中仅包含一座城市 S 由 T 出发形成了下一个层面（第二层）的 Cityblock,其中仅包含一座城市 S 对于每一个 Cityblock,它只有一个起点城市，所以我们看到在第二层面尽管都是 S，但我们还是让他形成了两个Cityblock, 以便向上回推的时候不会有混淆。 // 第三层 S 到 （M，T）， S 到 (M, T) // 第四层 M 到（Ｓ），　Ｔ到（Ｓ），　M 到（Ｓ），　Ｔ到（Ｓ），
到这里向上回推，有四条路径：
1)　S->M->S->M->S 翻转一下　S->M->S->M->S 　　那么这条路径是否为死循环呢？ 2) S->T->S->M->S S->M->S->T->S 这条符合要求 3) S->M->S->T->S S->T->S->M->S　　　到第二步就可以了，不必再走下去 4) S->T->S->T->S S->T->S->T->S　　　到第二步就可以了，不必再走下去
对于第一条路径我提了个问题，回答是：是也可以不是．因为他还可以继续往下发展也就是说，Ｓ-> M 可以无限次(n 趋向无限大)循环，但到　n+1 次时　Ｓ不再进入Ｍ，而是进入Ｔ然后由　Ｔ　又可以回到Ｓ．那么这样的话，怎么来理解最多经过的城市？这样看来，如果没有运行次数的限制，这样的题目变得多意性，没有解的意义．很简单，如果　a　与　b 之间有通路的话，那么他们永远可以在彼此之间来回．所以对于这道求进过最多城市的题，必须另外设置限制条件，比如在有限的步数内．不过，如果求最小经过城市次数，则不必增加附加条件．

瘋子愛老婆

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

Rain

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