`
huobengle
  • 浏览: 854592 次
文章分类
社区版块
存档分类
最新评论

USACO Section 3.3 Riding The Fences - 欧拉回路

 
阅读更多


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

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

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

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

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

Program:



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics