本文共 4224 字，大约阅读时间需要 14 分钟。

Description

Little Johnny has got a new car. He decided to drive around the town to visit his friends. Johnny wanted to visit all his friends, but there was many of them. In each street he had one friend. He started thinking how to make his trip as short as possible. Very soon he realized that the best way to do it was to travel through each street of town only once. Naturally, he wanted to finish his trip at the same place he started, at his parents’ house.

The streets in Johnny’s town were named by integer numbers from 1 to n, n < 1995. The junctions were independently named by integer numbers from 1 to m, m <= 44. No junction connects more than 44 streets. All junctions in the town had different numbers. Each street was connecting exactly two junctions. No two streets in the town had the same number. He immediately started to plan his round trip. If there was more than one such round trip, he would have chosen the one which, when written down as a sequence of street numbers is lexicographically the smallest. But Johnny was not able to find even one such round trip.

Help Johnny and write a program which finds the desired shortest round trip. If the round trip does not exist the program should write a message. Assume that Johnny lives at the junction ending the street appears first in the input with smaller number. All streets in the town are two way. There exists a way from each street to another street in the town. The streets in the town are very narrow and there is no possibility to turn back the car once he is in the street

Input

Input file consists of several blocks. Each block describes one town. Each line in the block contains three integers x; y; z, where x > 0 and y > 0 are the numbers of junctions which are connected by the street number z. The end of the block is marked by the line containing x = y = 0. At the end of the input file there is an empty block, x = y = 0.

Output

Output one line of each block contains the sequence of street numbers (single members of the sequence are separated by space) describing Johnny’s round trip. If the round trip cannot be found the corresponding output block contains the message “Round trip does not exist.”

Sample Input

1 2 1

2 3 2

3 1 6

1 2 5

2 3 3

3 1 4

0 0

1 2 1

2 3 2

1 3 3

2 4 4

0 0

0 0

Sample Output

1 2 3 5 4 6

Round trip does not exist.

分析

欧拉回路：对于一个图可以从一个顶点沿着边走下去，每个边只走一次，所有的边都经过后回到原点的路。（一笔画问题）。

欧拉回路的判定

有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。

无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

判断欧拉回路是否存在的方法

有向图：图连通，所有的顶点出度=入度。

无向图：图连通，所有顶点都是偶数度

这道题其实并不用判连通，因为常识告诉我们不会有一条路是封闭着的，所以我们只用判断每个定点的度数即可，由于本题是有向图，如果出现一个顶点的度数是偶数度，那就不会存在欧拉回路了

另外，选择好的数据结构很重要。

题目要求我们按照字典序最小的顺序来输出，我们考虑用栈的思想来存我们的路径至res数组中，最后用dfs找欧拉回路，然后逆序打印即可

AC

#include
   
    #include
    
     #include
     
      #define mst(a) memset(a,0,sizeof(a))using namespace std;const int maxn=20000+8;int angleNum[maxn]; //表示顶点度数int used[maxn];    //判断顶点是否走过int n,k;int res[maxn];      //路径数组int cnt=0;struct node{
           //结构体定义 起点和终点    int a;    int b;}rng[maxn];bool is_OK()   //此方法用于判定每个顶点的度数{
       for(int i=1;i<=n;i++)        if(angleNum[i]%2)   //如果存在一个顶点度数为偶数度，那么就不存在欧拉回路            return false;    //仅仅对于有向图而言        return true;}void dfs(int x){
       for(int i=1;i<=k;i++)    {
           if(!used[i]&&(rng[i].a==x||rng[i].b==x))   //这里处理有点特殊，我们不确定        {
   										   //走的是每个分支的起点还是终点            used[i]=1;            dfs(rng[i].a+rng[i].b-x);            res[++cnt]=i;        }    }}int main(){
       ios::sync_with_stdio(false);   //cin提速    cin.tie(0);    int x,y,z;    while(cin>>x>>y&&(x+y))    {
           int point=min(x,y);         //求出我们的源点        n=max(x,y);        mst(angleNum);        mst(used);        cnt=k=0;        do{
               cin>>z;            rng[z].a=x;            rng[z].b=y;            ++k;            angleNum[x]++; angleNum[y]++;            n=max(n,max(x,y));  //求出最大的顶点数        }while(cin>>x>>y&&(x+y));        if(!is_OK())        {
               cout<<"Round trip does not exist."<
      
       =1;i--)     //逆序输出路径        {
               if(i!=1)           cout<
       
        <<" ";           else            cout<
        
         <
        
       
      
     
    
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/97623783 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！