很烦……做不了

楼主 不要 急嘛!!

其实不是你不会做.而是要有好的心态 才能有 好的收获啊!

啊，楼上的大师说得好抽象啊，IOI的题，一题就能爆头，冷静不了。

昨天下线后就一直在想这道题，思路变得交错复杂起来，一时间想法很多。脑子的多线程运算好像混乱起来。我静静坐了很久，在想如何去写这个程序，或者说如何用C++ 来模拟这个推理过程。

我的数据结构知识很不到位，也不清楚树有多少种类，用怎样的方法来描述一个多分枝树呢？

确切的程序还没有写完，今天上来一看，你上传了别人的论文，在写完程序之后再来看看。

关于这道题目，我的想法是这样的。

我们知道我们有一些城市（City），每个城市都有它的邻居城市，也就是可以互通的城市。

其实一个城市就是一个节点。现在我们有一个起点城市，从这个城市出发我们可以到达他的邻居城市。

这个起点城市就是这棵树的顶端。对于顶端而言，它自身不再有起点城市。

从起点城市可以到达的城市，就是他的邻居城市。如果这个起点城市有两个邻居，那么，位于这棵树的第二层，就是他的那两个邻居城市。现在从第二层出发，向树的第三层发展。位于第二层的每一个节点都有其自身的邻居节点，但不意味着，他的所有邻居节点，都可以成为他的下一层节点。可以发展下去的前提是，这个邻居城市与他的起点城市的以上所有相关起点城市相比较，如果名字都不相同，那么 OK，他可以发展为下一层节点，如果与最初的那个城市，即位于树的顶端的那个城市的名字相同，并且，在一路比较过程中，发现有那个拐点城市，那么那个城市也可以发展到树的下一层，但是它已经是这条支路的末端了。依照这样的原则，这棵树逐渐往下发展，当所有的支路都不能形成 起点，拐点，起点那么一条路，那么此题无解，否则，那条发展得最长的支路便是我们的解。

想法就是这样，接下来我们便要设计我们的代码。

位于这棵树上的每一个节点，就是一个城市。

树是包含了这些城市的一个结构。树的形成依照某个游戏规则。

如果我们写了一个class City ， 另外写了那个class CityTree 而 createCityTree 便是我们最终要实现的。

今天我写了那个class City ,他看起来是这样的。其中有一个函数还有问题。

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

class City; class Cityblock; typedef vector<string> VCSTR; typedef vector<City> VCC; typedef vector<Cityblock> VCCB;

class City { private: string name; // every city has his name. City * start; // point to his startcity. int depth; // his level bool urStartCity; // to indicate, wheather he is a Urstartcity bool turnningCity; // to indicate, whether he is a turnningcity bool iAmTheLastOne; // to indicate, that this city is the last element in a road VCSTR vcStrNeighborCity; // a container to keep the name of the neighborcity VCC visitcities; // a container to keep all his childrenCities public: City(); // default constructor City(const string & cityname); // initialize the object with the name void set_as_startcity(); // in this program, we have a Urstartcity void set_as_turnningcity(); // and a turnningcity, bool is_UrStartCity(); // the city should tell us, whether he is a Urstartcity bool is_TurnningCity(); // the city should also tell us, whether he is a turnningcity bool is_theLastOne(); // the city should tell us, whether he is the last one in a road. string get_name(); // we want know, what is his name. City * get_startCity(); // we want know, what is his startcity. VCSTR get_Neighborinfo(); //for every city there are some neighborcity belong to him. int get_depth(); // in this City_Tree, every city will be located in position(in a level) void set_depth(); // to decide which level belong to him, we ask first, if you are the urstartcity, // when yes, your depth is 0, otherwise, your depth is a step more than your startcity. void set_neighbor(const string & a_city); // add the name of neighborcity in the neighborcity vector bool set_visitcity(); // this method is very import, every city has his neighborcity, // but it doesn't mean, all his neighborcity would be his visitcity. // only the city, who has not appear in the road, or the urstartcity. // because the urstartcity can be at begin, can also be at the end. friend class Cityblock; // in a cityblock will save all the cities, that belong to a same level. //....... may be };

City::City() { name = " "; start = NULL; urStartCity = false; turnningCity = false; iAmTheLastOne = false; }

City::City(const string & cityname) { name = cityname; start = NULL; urStartCity = false; turnningCity = false; iAmTheLastOne = false; }

int City::get_depth() { return depth; }

string City::get_name() { return name; }

VCSTR City::get_Neighborinfo() { return vcStrNeighborCity; }

City * City::get_startCity() { return start; }

bool City::is_theLastOne() { return iAmTheLastOne; }

bool City::is_TurnningCity() { return turnningCity; }

bool City::is_UrStartCity() { return urStartCity; }

void City::set_as_startcity() { urStartCity = true; }

void City::set_as_turnningcity() { turnningCity = true; }

void City::set_depth() { if(urStartCity) depth = 0; else { depth = start->get_depth() + 1; } }

void City::set_neighbor(const string & a_city) { vcStrNeighborCity.push_back(a_city); }

// This Method has still problem.

bool City::set_visitcity() { for(int i = 0; i<vcStrNeighborCity.size(); i++) { City temp = *this; bool visited = false; while(!temp.is_UrStartCity()) { temp = *(temp.get_startCity()); if(temp.is_UrStartCity()) { if(vcStrNeighborCity.at(i) == temp.get_name()) { break; } } else { if(vcStrNeighborCity.at(i) == temp.get_name()) { visited = true; break; } } } if(!visited) { visitcities.push_back(City(vcStrNeighborCity.at(i))); visitcities.end()->set_depth(); } } if(visitcities.empty()) return false; else true; }

我讲的比较抽象，不知道大家能不能理解。

C++ 是非常适合写模拟过程的程序的。如果大家还能回忆起来，那个生母牛问题我就写了一个C++ 程序，在程序运行之前我并不知道，程序的运行结果。我只是用代码实现逻辑或物理模拟过程。而写C程序，往往是已经清楚了事物的发展规律，比如那个母牛问题，如果写C 程序，就是一个数列公式在一个for loop 中。但前提是你必须清楚问题的本质可以归纳为一个数列公式。如果不清楚，便很难着手了。

这个程序我会尽力写出来，不知道那篇论文写的代码是C 代码还是C++ 代码。

那是pascal语言，论文中没什么新鲜的东西，呵呵，不过难为这个小作者了^_^.

live41,还没解决啊？这个graph theory要C中是比较难问题（我的感觉一个字"烦")，我不知道C++处理起来是否会简单点。

上次那个没有回溯，所以你改动一下航线的次序就不一定能找到解。下面这个是用了回溯，只要有解，一定能找到，但不一定是最佳的。你两个程度一起比较一下我在程式中加上演示回溯过程，改了改你给的例子，你自己也可改动一下例子来看看回溯是怎么进行的（可以在程序加上打印各种变量的语句)，但是例子要符合题意。

说实话我从来没有在自己写的程序中加了这么多的注解,关于搜索方法有很多，什么深度，广度，探试，最小代价，路径剪除，节点摘除..............技巧很多，但是，没有一种方法是可以“绝对地”用在“任何”问题能找出最佳的解，除非是穷举！但是也有一个问题，有个术语叫“组合暴炸”，不用我多说你也知道这类问题是不可能用穷举解决的。所以用什么方法与你的问题相关，取决你的数据组合的特点，对此问题“最佳搜索方法”我在程序注解中也讲了。

你搞来搞去的，我不知道你到底学什么，如果是C++，那么，我建议你只看我的算法（这次我加了很多注解，而改了以前的习惯，自认为写得比较容易看得懂^_^,再看不懂），C++怎么写还得KAI出手

#include <stdio.h> #include <string.h> #include <alloc.h>

struct Route { char from[16]; char to[16]; int flag ; } ; typedef struct Route ROUTE ;

int top0=-1,top1=0; int N,V; /*前一个为city个数,后一个为航线个数*/ char (*stack_temp)[16],(*stack_end)[16]; /*定义二个有16个char 型成员的指针*/ /*(*stack_end)[16]本程序没用上，是用作保存最佳路径的*/ int Flag=0;/*定义一个旗标，当flag=0时，从西往东走,当flag=1时从东往西走*/ char city[2][16];/*用于储存最西及最东的city */ ROUTE * route;/*定义一个结构体指针*/ /*注意：这里变量都定义为全局变量是为了便于程序阅读*/

void Rout(char *temp); int find(char *temp); void push(char *city); void pop(char *city); int main(void) {

int i,j ; char temp[16];

while(scanf("%d%d",&N,&V)!=EOF) /*读入城市总数N,航线总数V*/ { route = (ROUTE*)malloc(V*sizeof(ROUTE)); /*给route分配一个V*sizeof(ROUTE)大小的空间*/ stack_temp = (char (*)[16])malloc((N+1)*16*sizeof(char )); /*这个饯用作查找*/ stack_end = (char (*)[16])malloc((N+1)*16*sizeof(char )); /*这个饯用作储存最长路线*/ /*建立两个大小为char型 (N+1)*16的空间*/

scanf("%s",city[0]); /*读入第一个城市名（最西）*/ for(i=1;i<N;i++) { scanf("%s",city[1]); /*只读入保存最东的城市名，因为中间的城市名在本程序用不到^_^*/ /*如果你想找最优解，那么都保存下来，因为按题意这些城市名*/ /*是从西至东的，那么，我们可假定：找下一个城市时尽可能取靠*/ /*前面的城市（即距当前城市最近的)，这样求出的解是最佳的*/ }

for(j=0;j<V;j++) { scanf("%s%s",route[j].from,route[j].to); /*读入保存航线*/ route[j].flag=1 ; /*flag标志置1,表示该航线处在可用状态,当flag置0时表示已用过一次不能再用*/ }/*建一个航班库*/

for(j=0;j<V;j++) { printf("%s %s\n",route[j].from,route[j].to); /*读入保存航线*/ } sleep(2);

strcpy(temp,city[0]);

Rout(temp);

free(stack_temp); free(stack_end); free(route); top0=-1; Flag=0; } } void push(char *city) { if(top0<(N+1)) { top0++; strcpy(stack_temp[top0],city); /*压*/

} else { printf("Stack full.\n"); return ; } } void pop(char *city) { if(top0>0) { top0--; strcpy(city,stack_temp[top0]); /*弹*/ top0--; } else { printf("Stack underflow.\n"); return ; } }

int find(char *temp) /*查找从temp城市出发的一下个城市*/ { int i;

if(!Flag) { for(i=0;i<V;i++) { if(!(strcmp(temp,route[i].from))&&route[i].flag==1) /*当Flag=0时是西东走向，所以比较temp与from*/ { route[i].flag=0 ; strcpy(temp,route[i].to); /* 找到压贱的城市*/ return 1; } } } else { for(i=0;i<V;i++) { if(!(strcmp(temp,route[i].to))&&route[i].flag==1) /*当Flag=1时是东西走向（回程)，所以比较temp与to*/ { route[i].flag=0 ;

strcpy(temp,route[i].from); return 1; } } } return 0;/*没找到则返回0*/ } void Rout(char *temp) { int i;

push(temp);

printf("top= %d temp = %s\n",top0,stack_temp[top0]); sleep(4);

if(!strcmp(stack_temp[top0],city[1])) /*如果到达最东的城市*/ { Flag=1;

} if(top0>1)if(!strcmp(stack_temp[top0],city[0])) /*如果回到最西的城市*/ { for(i=0;i<=top0;i++)printf("%s ",stack_temp[i]); printf("\n\n"); return ; } if(find(temp))Rout(temp); /*find()返回1，表示此节点有解*/ else { /*find()返回0，表示此节点无解*/ pop(temp);/*弹出前一个节点(城市)*/ Rout(temp);/*用弹出的前一个节点(城市)，再找*/ } }

没给完整的答案，还是希望你自己解决^_^

改动后的示例如下，用法还是象上次一样，最好你自己能在纸画出这个图看看：

10 11 Vancouver Yellowknife Edmonton Calgary Gtt KLL Winnipeg Toronto Montreal Halifax Edmonton Yellowknife Yellowknife Gtt Gtt KLL Toronto Halifax Montreal Halifax Edmonton Calgray Vancouver Edmonton Vancouver Calgary Edmonton Montreal Calgary Winnipeg Winnipeg Toronto

感激的话就不多说了，总之谢谢楼上两位是世外高人不厌其烦的帮忙。我仔细研究一下你们的代码，现在在学校别人的机上，由于题目太难，所以又延期了，暂时不用交，呵呵，赚到了……