[問題] 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