John's trip
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 5455
Accepted: 1774
Special Judge
Description
Little Johnny has got a new car. He decided to drivearound 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 startedthinking how to make his trip as short as possible. Very soon he realized thatthe 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 hisparents' 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 townhad different numbers. Each street was connecting exactly two junctions. No twostreets in the town had the same number. He immediately started to plan hisround trip. If there was more than one such round trip, he would have chosenthe one which, when written down as a sequence of street numbers islexicographically the smallest. But Johnny was not able to find even one suchround trip.
Help Johnny and write a program which finds the desired shortest round trip. Ifthe round trip does not exist the program should write a message. Assume thatJohnny lives at the junction ending the street appears first in the input withsmaller number. All streets in the town are two way. There exists a way fromeach street to another street in the town. The streets in the town are verynarrow and there is no possibility to turn back the car once he is in thestreet
Input
Input file consists of several blocks. Each blockdescribes 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 bythe 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 ofstreet numbers (single members of the sequence are separated by space)describing Johnny's round trip. If the round trip cannot be found thecorresponding output block contains the message "Round trip does notexist."
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.
Source
Central Europe 1995
題意：
x,y,z表示起點，終點和這條邊的編號，從圖的起點出發，問是否能訪問完所有邊，然後回到起點，訪問的相同邊根據字典序列來訪問。
解題思路：
這個題目可以用歐拉回路來決解，首先根據輸入建立圖，保存圖中每條邊的編號，起點，終點，記錄邊數和點數，用歐拉回路來判斷該圖是否存在歐拉回路，如果存在，則遞歸遍歷每一條邊，直到所有邊都遍歷完成。遍歷的起點為上一條邊的終點。
代碼：
#include <iostream>
#include<stdio.h>
#include<string.h>
#define MAX 50
using namespace std;
struct edge
{//存邊
int start,end;
};
edge e[2000];//邊數
int g[MAX][MAX];
int indegree[MAX];
int outdegree[MAX];
int temp[MAX];
int visited[2000];//記錄某節點是否被訪問過
int t;
int v,es;//記錄點數和邊數
//從起點s開始遍歷每一條邊
void euler(int s)
{
for(int i=1;i<=es;i++)
{
//該條邊沒有被訪問過，並且該邊的起點或者終點是要訪問的點s
if(visited[i]==0 && (e[i].start==s||e[i].end==s))
{
visited[i]=1;//訪問該條邊
euler(e[i].start+e[i].end-s);//從起點訪問到終點，再以終點為起點開始訪問下一條邊
temp[t]=i;
t++;
}
}
}
int main()
{
int x,y,z;
int i,j;
int flag=0;
while(true)
{
int start;
memset(g,0,sizeof(g));
memset(visited,0,sizeof(visited));
memset(indegree,0,sizeof(indegree));
memset(outdegree,0,sizeof(outdegree));
v=0;
es=0;
t=0;
while(true)
{
scanf("%d%d",&x,&y);
if(x==0 && y==0)
{
flag++;
if(flag==2)
return 0;
break;
}
//求出起點，x，y中的最小值
start=x;
if(start>y)
start=y;
flag=0;
scanf("%d",&z);
g[x][y]=1;
g[y][x]=1;
e[z].start=x;//圖已經的連通圖，不用再判斷是否連通
e[z].end=y;
//計算邊數和點數
if(es<z)
es=z;
if(v<x)
v=x;
if(v<y)
v=y;
//記錄出度和入度，用來判斷歐拉路
indegree[x]++;
outdegree[y]++;
}
//判斷是否是歐拉回路
for(i=1;i<=v;i++)
{
for(j=1;j<=v;j++)
{
if(g[i][j]==1 && (outdegree[j]+indegree[j])%2!=0)
{
printf("Round trip does not exist.\n");
break;
}
}
if(j<=v)
break;
}
if(i<=v)
continue;
euler(start);
for(i=es-1;i>=1;i--)
{
printf("%d ",temp[i]);
}
printf("%d\n",temp[0]);
}
return 0;
}
作者：CSDN515
