題意:
給你一個無向圖,每條邊有cost,現在問如果不走已經走過的邊,則從S到T,然後再從T到S的最少cost是多少,如果無法達成則輸出"Back to jail"。
想法:
最小cost最大流,S到T再從T到S,也就是T當作源點,S當作匯點,從T流到S,看是否能流過去2條,如果能則輸出min_cost,否則輸出"Back to jail"。
因為同一條邊不能重複走,因此可以用一個二維矩陣used[][],在SPFA找"正向邊"的時候檢查used[i][j]!=true,除了code 82行和96行之外,其他都和MCMF模板一樣。
沒有留言:
張貼留言