本文鏈接:http://www.cnblogs.com/Ash-ly/p/5398549.html

題意：

　　Johnny 有了一臺(tái)新車(chē)，他想去訪問(wèn)他所有的朋友(赤裸裸的炫耀？),他的朋友有很多，住在城市中的街道上，于是他就開(kāi)始規(guī)劃自己的路了，在這個(gè)城市中有很多街道，他想找一個(gè)路徑，這個(gè)路徑經(jīng)過(guò)一個(gè)街道僅一次，但能訪問(wèn)完他所有的朋友，他從他父母家出發(fā)，并且回來(lái)時(shí)也必須在他父母家。

　　在這個(gè)城市中，一共有N(N < 1995)個(gè)街道，共有M(M <= 44)個(gè)轉(zhuǎn)折點(diǎn)，轉(zhuǎn)折點(diǎn)就是一個(gè)街道的兩端，每條街道和轉(zhuǎn)折點(diǎn)的編號(hào)都不同。如果在一個(gè)轉(zhuǎn)折點(diǎn)有多種選擇，他會(huì)優(yōu)先選擇街道編號(hào)比較小的。

　　讓你幫忙寫(xiě)一個(gè)程序，找到這個(gè)路徑，如果找不到就打印“Round trip does not exist.”，從 1 號(hào)轉(zhuǎn)折點(diǎn)出發(fā)，最后必須回到 1 號(hào)轉(zhuǎn)折點(diǎn)，經(jīng)過(guò)每條街道僅一次，訪問(wèn)完他所有的朋友，街道是雙向的，但是不能掉頭。

思路：

　　把城市想象成一個(gè)圖，轉(zhuǎn)折點(diǎn)即是點(diǎn)，街道即是邊，從某一起點(diǎn)出發(fā)，訪問(wèn)所有邊且每條邊僅訪問(wèn)一次，再回到起點(diǎn)，很自然想到歐拉回路。首先需要判斷是否存在歐拉回路，無(wú)向圖的每個(gè)點(diǎn)的入度為偶數(shù)就一定存在歐拉回路。然后由于是無(wú)向圖，在存儲(chǔ)邊的時(shí)候需要正反各儲(chǔ)存一次，訪問(wèn)一條邊，也要同時(shí)刪除兩條邊，正反各一條。題目還有求輸出字典序最小的，這里可以在選擇邊的時(shí)候每次選擇編號(hào)最小的那個(gè)遍歷，然后回溯回來(lái)時(shí)，也是最短的。

代碼：

/* POJ 1041 algs:鏈?zhǔn)角跋蛐?存圖) + 歐拉回路(找圖) time:2016/4/25 */ #include <stdio.h> #include <string.h> #include <iostream> #include <math.h> #include <queue> #include <stack> #include <algorithm> using namespace std; int V,E; const int maxV = 44; const int maxE = 1995; int head[maxV + 7]; int visit[2 * maxE + 7]; //標(biāo)志邊是否被訪問(wèn) int degree[maxV + 7]; //每個(gè)點(diǎn)的度 struct EdgeNode {int to;int w; //題目所給邊的編號(hào) int next; }edges[2 * maxE + 7];int Max(int x, int y, int z){ return ( x > y ? (x > z ? x : z) : (y > z ? y : z) ) ; }int isEulur() //是否是歐拉回路 無(wú)向圖不含有度數(shù)為奇數(shù)的點(diǎn) {for(int i = 1; i <= V; i++)if(degree[i] & 1) return 0;return 1; } void debugio(); void debugG(); void debugvi();stack<int> ansE;//用一個(gè)棧來(lái)存放答案 void eulurDFS(int now) {for(int i = 1; i <= degree[now]; i++) //每個(gè)點(diǎn)可選擇下一個(gè)擴(kuò)展節(jié)點(diǎn)的個(gè)數(shù) {int min = maxE + 7; //用于找到編號(hào)最小邊 int tmpvst = head[now]; //編號(hào)最小邊的下標(biāo) for(int k = head[now]; k != -1; k = edges[k].next)//在所有相鄰的邊中找編號(hào)最小邊 {if(!visit[k] && edges[k].w < min)min = edges[k].w, tmpvst = k;}if(visit[tmpvst] || min == maxE + 7) continue;visit[tmpvst] = 1; //標(biāo)志找到的邊為已訪問(wèn),在鏈?zhǔn)角跋蛐侵忻織l邊被存儲(chǔ)了兩次 tmpvst & 1 ? visit[tmpvst + 1] = 1 : visit[tmpvst - 1] = 1;--degree[now],--degree[edges[tmpvst].to]; //訪問(wèn)一條邊,則這條邊兩端點(diǎn)的度數(shù)各減一、否則TLE！！ eulurDFS(edges[tmpvst].to);//訪問(wèn)編號(hào)最小邊 ansE.push(tmpvst); //回溯的過(guò)程中記錄答案 } }int main() {//freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);while(true){int x, y;scanf("%d%d", &x, &y);if(!(x || y)) break;E = 0;V = 0;memset(&edges, 0, sizeof(EdgeNode));memset(head, -1, sizeof(head));memset(degree, 0, sizeof(degree));while(x || y){int z;scanf("%d", &z);++E;edges[2 * E - 1].to = y; //無(wú)向圖每條邊儲(chǔ)存兩次 edges[2 * E - 1].w = z;edges[2 * E - 1].next = head[x];head[x] = 2 * E - 1;edges[2 * E].to = x;edges[2 * E].w = z;edges[2 * E].next = head[y];head[y] = 2 * E;degree[x]++; //度數(shù) degree[y]++;V = Max(V, x, y); scanf("%d%d", &x, &y);}if(isEulur()){memset(visit, 0, sizeof(visit));eulurDFS(1);int pe = 0;while(!ansE.empty()){printf( pe++ ?" %d":"%d", edges[ansE.top()].w);ansE.pop();}printf("\n");}else //不存在歐拉回路 printf("Round trip does not exist.\n");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Ash-ly/p/5398549.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1041 John's trip(欧拉回路)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。