[问题] UVA10735 Euler Circuit

楼主: kilettt (@@)   2015-12-20 04:52:26
开发平台(Platform): (Ex: VC++, GCC, Linux, ...)
C++
额外使用到的函数库(Library Used): (Ex: OpenGL, ...)
问题(Question):
这题先把无向边随意定向,在计算包括有向边的情况下,每个点的出度数跟入度数的差值
每次调整无向边的方向会使差值更动2,若有差值为偶数,则图中不存在欧拉循环
接着在图中多两个点s,t,代表网络流图中的源点还有汇点
计算原图中每点的差值除2,得到的值若为正(出>入),则从s点
多一条容量上限为此值的边连到此点,若为负值则从此点连一条容量上限为此值绝对值的
边至t点,移除原图所有的有向边,所有无向边容量上限为1,计算s->t的最大流量
若最大流量与s点连出去的边的容量上限总合相同,则把流过的边方向调换,在加上原
本的有向边,可以找到欧拉圈。
以上是程式大致的处理过程.... 跑sample测资会对,但交上UVA得到TLE的结果...
跑网络流及找欧拉圈都用DFS去搜...
程式码加上许多注解,望请大大们不吝指教 3Q
喂入的资料(Input):
UVA SAMPLE测资
预期的正确结果(Expected Output):
错误结果(Wrong Output):
TLE
程式码(Code):(请善用置底文网页, 记得排版)
http://tinyurl.com/phbvn8z
补充说明(Supplement):

Links booklink

Contact Us: admin [ a t ] ucptt.com