0w1

Negative Cycle

UVA 11478 Halum ( 二分 + 差分約束系統 )

UVa Online Judge 由於順序無關,我們可以將每個操作獨立出來,令 dsum( u ) 為作用在 u 上的所有 d 權和,那麼對於一個邊 u -> v,它的最終邊權是 w( u, v ) + dsum( u ) - dsum( v )。由於題目要求最小值極大化,我們考慮二分搜尋,假設最小值的最大可能為…

UVA 11090 Going in Cycle!! ( 二分 + SPFA判負圈 )

UVa Online Judge 要求平均權值極大化,一個很常用的技巧是假設平均權值為 x,如果我們將全部的值減去 x以上的值,或全部減去 x - 1以下的值,前者和後者的差異在總和小於 0和大於 0。題目特別要求的是環,所以我們發現我們可以二分搜尋最接近正確答案的 x,…