題目鏈接：點(diǎn)擊查看

題目大意：給出一張無(wú)向圖，要求從起點(diǎn)開(kāi)始遍歷一遍所有的邊，最后再回到起點(diǎn)，題目要求輸出任意一組方案

細(xì)節(jié)：

起點(diǎn)不是點(diǎn)1，而是第一條邊中兩個(gè)端點(diǎn)中嬌小的一個(gè)點(diǎn)

給出的x y z代表的是點(diǎn)x到點(diǎn)y由id為z的邊連接

最后答案要求輸出的是邊的id

題目分析：歐拉回路模板題，不過(guò)是開(kāi)一個(gè)vis數(shù)組用來(lái)記錄id的訪問(wèn)情況就好了，明明感覺(jué)這個(gè)題用鄰接表更好寫(xiě)，為什么網(wǎng)上那么多人都用了鄰接矩陣呢？菜雞表示不明白

期末考試前的最后一道算法題了，得認(rèn)真復(fù)習(xí)了，不然真得掛科了。。可能接下來(lái)的幾天復(fù)習(xí)煩了會(huì)去找?guī)讉€(gè)cf的題做做吧。。好好復(fù)習(xí)，天天向上

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=50;const int M=2e3+100;struct Node {int to,w;Node(int TO,int W){to=TO;w=W;} };vector<Node>node[N];int du[N];bool vis[M];void dfs(int u) {for(int i=0;i<node[u].size();i++){int id=node[u][i].w;if(!vis[id]){vis[id]=true;dfs(node[u][i].to);printf("%d ",id);}} }void init() {for(int i=0;i<N;i++)node[i].clear();memset(du,0,sizeof(du));memset(vis,false,sizeof(vis)); }bool check() {for(int i=0;i<N;i++)if(du[i]&1)return false;return true; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int x,y,st;while(scanf("%d%d",&x,&y)!=EOF&&x+y){init();int z;scanf("%d",&z);st=min(x,y);node[x].push_back(Node(y,z));node[y].push_back(Node(x,z));du[x]++;du[y]++;while(scanf("%d%d",&x,&y)!=EOF&&x+y){scanf("%d",&z);node[x].push_back(Node(y,z));node[y].push_back(Node(x,z));du[x]++;du[y]++;}if(!check())puts("Round trip does not exist.");else{dfs(st);printf("\n");}}return 0; }

?

總結(jié)

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

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