0w1

System of Difference Constraints

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

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