UVa Online Judge 很明顯是一個類似次小生成樹的問題，因為只刪除一個邊，我們考慮一一枚舉要刪除的邊互相比較。將每個點對的最小瓶頸路徑預處理 O( n * n )，檢查刪除後的權值總和就能達到 O( 1 )。總複雜度 O( m lg m + n * n )。關於最小瓶頸路徑可以看這…

訓練指南裡提出了幾個經典的生成樹問題，我想做一點整理。 首先提出了最小生成樹有兩個性質： 1. 切割性質：任一個圖 G的子集 G'非空且不為 G本身，則其中一個端點在 G'裡，另一個端點在 G 的邊裡權值最小的必然會包含於 G的最小生成樹裡。 2. 迴路性質：任…

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

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

UVa Online Judge 從終點逆推回去更新最小值。具體來說用 Priority First Search，尋找目前還沒用過的擁有最小值的節點來更新它所有可能的前驅點。打印路徑的時候只要反方向( 其實也就是順向 ) 檢查哪些點是可通行的，取其字典序最小慢慢遞進就行了。複雜度…