CF 24A: Ring Road - 環圖遍歷最小反轉代價

問題描述

n 個城市成環，每條雙向路變為單向，給定方向和反轉代價。求最小總代價使圖強連通（任意城市可達）。

觀察

環上強連通 ⇔ 所有邊同向（順時針或逆時針）。
對每條邊，若方向與順時針一致代價 0，否則代價 c_i。順時針總代價 = 所有逆向邊代價和。逆時針總代價 = 總代價和 - 順時針代價。答案取較小者。

實現

建圖：對每條輸入邊 (a,b,c)，添加 a→b 權 0，b→a 權 c。從 1 出發 DFS 遍歷環（每節點度數 2），累加邊權得到順時針代價。答案 = min(sum, total-sum)。