[問題] UVA10735 Euler Circuit
開發平台(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)：
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.113.173.57
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1450558349.A.982.html
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
