USACO Section 3.3 Riding The Fences - 欧拉回路

这题要求一条路径走完所有的边并且不重复经过任意一条边...很典型的欧拉回路问题..关于欧拉回路本节的TXT就有介绍算法了...

首先一个连通的无向图如果所有的点度数位2存在欧拉回路(想象一个首尾相接的圈,如果两点间不止一条边,那么稍微变化下也能到所有点)...如果一个连通无向图有两个点的度为奇数也存在欧拉回路.并且这个回路一定是以这两点为起点终点的(想象一个直线...两端的度为1,中间的度都为2)...如果不止2个点的度为奇数..那么不存在欧拉回路..觉得这个还是很好想到和理解吧~

假设一个连通图存在欧拉回路...USACO提供的方法:(不完整的一部份..)

为何用这个方法能求出欧拉回路~~跟雄哥讨论了下说这实际上是一个作欧拉回路的逆过程...

PS: 最近又是CET又是期末考试的...生活都很混乱阿~~题也没A啥的说...本周五解脱~T_T...

Program:

/* ID: zzyzzy12 LANG: C++ TASK: fence */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<algorithm> #include<queue> #define oo 1000000000 #define ll long long using namespace std; int F,arc[505][505],ans[1030],m,mm,a[505],t; bool used[505]; stack<int> mystack; void getanswer() { int i,h,num=F+1; while (!mystack.empty()) mystack.pop(); memset(used,0,sizeof(used)); mystack.push(t); while (!mystack.empty()) { h=mystack.top(); if (!a[h]) { ans[num]=h; mystack.pop(); num--; continue; } for (i=mm;i<=m;i++) if (arc[i][h]) break; a[h]--; a[i]--; mystack.push(i); arc[i][h]=--arc[h][i]; } } int main() { freopen("fence.in","r",stdin); freopen("fence.out","w",stdout); memset(arc,0,sizeof(arc)); scanf("%d",&F); m=0; mm=oo; for (int i=1;i<=F;i++) { int x,y; scanf("%d%d",&x,&y); arc[x][y]=++arc[y][x]; if (x>m) m=x; if (y>m) m=y; if (x<mm) mm=x; if (y<mm) mm=y; a[x]++; a[y]++; } for (t=mm;t<=m;t++) if (a[t]%2) break; if (t==m+1) t=1; getanswer(); for (t=1;t<=F+1;t++) printf("%d\n",ans[t]); return 0; }