先把題目簡化： 有 ABCD 四個地方各多一輛車，PQRS四個地方各少一輛車。 一樣要找出最少的代價把車子補滿。代價如下： P Q R S A 7 5 4 5 B 2 8 3 4 C 3 3 4 7 D 6 5 2 2 不過，在你準備找出最好的組合時，你發現一件事， 如果在 ABCD 把車賣掉，會有 u_A, u_B, u_C, u_D 的進帳 如果在 PQRS 直接買車，要花 v_P, v_Q, v_R, v_S 如果 u_i + v_j < c_ij ， 那與其把車從 i 運到 j，不如把 i 的車賣掉，在 j 直接買， 甚至，當 u_i + v_j <= c_ij 對所有的 i, j 都成立時， 就不用煩腦這個問題了，直接賣掉再買就好。 很剛好的是，你是一個車商，負責車子的買、賣，而你在這幾個地方也都有據點， 所以，你想要找到一個定價，使得你可以賺最多錢， 而為了讓他們把所有的車都讓你處理，你當然要讓 u_i + v_j <= c_ij 都成立 有一個顯然會成立的定價方法是： u_i = 0, v_j = min{c_ij} 不過，這可能不是最好的定價方法，你希望可以賺更多的錢。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 看到這裡，可能會有人問，車商的定價到底和原本的問題有什麼關係？ 假設 u_i + v_j <= c_ij 對所有 i, j 都成立 那 sum {u_i} + sum {v_j} <= 任何一種運送方式的成本 假設 c_AP c_BQ c_CR c_DS 是你選的運送方式，那麼 u_A + v_P <= c_AP u_B + v_Q <= c_BQ u_C + v_R <= c_CR u_D + v_S <= c_DS sum {u_i} + sum {v_j} <= 你的成本 換言之，任意符合這樣條件的 u, v ，上面的等式都成立。 而我們知道運送成本有最小值，而這個就是 sum {u_i} + sum {v_j} 的最大值 而且，等號是可以成立的，假設剛剛的 c_AP + c_BQ + c_CR + c_DS 是最小， 那我們讓 u_i = 0, v_j = c_ij (c_ij 是被選到的配對) 就是一個 sum {u_i} + sum {v_j} = c_AP + c_BQ + c_CR + c_DS 的例子 也就是說，如果我們可以找到 sum {u_i} + sum {v_j} 的最大值 那這個值就是運送成本的最小值，兩個問題其實是一樣的。 現在，讓我們來解解看新的問題， P Q R S A 7 5 4 5 B 2 8 3 4 C 3 3 4 7 D 6 5 2 2 我們先找一個可能的 u, v 組合，然後再慢慢的把他變大。 我們就選個 u_i = 0, v_j = min {c_ij} 吧， 括號中的是 u_i 或 v_j ，中間的表格則是 c_ij - u_i - v_j P(2) Q(3) R(2) S(2) A(0) 5 2 2 3 B(0) 0 5 1 2 C(0) 1 0 2 5 D(0) 4 2 0 0 因為我們知道最大值發生時，會有 c_ij = u_i + v_j （ij 是我們選中的匹配） 也就是上面表格中的 0 ，如果我們可以找到四個 0 ，他們都在不同的行和列， 那我們就完成了，可是，現在顯然無法達到，所以，我們要調整我們的 u, v ， 造成更多的 0 ，以找到更多的匹配，可是調整的時候， 還要要有 u_i + v_j <= c_ij for all i, j 調整的方法是： 先選出最少的行和列，使得所有的 0 都在這幾個行或列中，比如： P(2) Q(3) R(2) S(2) P(2) Q(3) R(2) S(2) A(0) 5 2 2 3 A(0) 5 2 2 3 B(0) 0 5 1 2 或是 B(0) 0 5 1 2 C(0) 1 0 2 5 C(0) 1 0 2 5 D(0) 4 2 0 0 D(0) 4 2 0 0 都用了三個行或列就包含了所有的 0 ，現在，我們在沒被覆蓋的格子中，選出最小的， 右邊被選出的行、列為 Z = {D, P, Q} ， (Z 沒有什麼特別的意義，只是集合的 S 被用掉了) 而在沒被覆蓋的格子中，最小的是 1 ，令這個值為 e 我們順便定義 X = {A, B, C, D} , Y = {P, Q, R, S} 現在要來調整 u, v 了 對 x_i \in (X ∩ Z) , u_i <- u_i - e y_j \in (Y \ Z) , v_j <- v_j + e (x <- .... 代表新的 x 的值為 ....) 以現在的狀況來說， X ∩ Z = {D}, Y \ Z = {R, S} 所以， u_D <- u_D - 1 = 0 - 1 = -1 v_R <- v_R + 1 = 2 + 1 = 3 v_S <- v_S + 1 = 2 + 1 = 3 新的表格為： P(2) Q(3) R(3) S(3) A( 0) 5 2 1 2 B( 0) 0 5 0 1 C( 0) 1 0 1 4 D(-1) 5 3 0 0 重複上面的動作，再找出最少的行和列來包括所有的 0 P(2) Q(3) R(3) S(3) A( 0) 5 2 1 2 B( 0) 0 5 0 1 C( 0) 1 0 1 4 D(-1) 5 3 0 0 Z = {B, C, D} e = 1 X ∩ Z = {B, C, D} Y \ Z = {P, Q, R, S} u_B <- u_B - 1 = -1 u_C <- u_C - 1 = -1 u_D <- u_D - 1 = -2 v_P <- v_P + 1 = 3 v_Q <- v_Q + 1 = 4 v_R <- v_R + 1 = 4 v_S <- v_S + 1 = 4 P(3) Q(4) R(4) S(4) A( 0) 4 1 0 1 B(-1) 0 5 0 1 C(-1) 1 0 1 4 D(-2) 5 3 0 0 現在我們可以找到一個完美匹配, A-R 、B-P 、C-Q 、D-S 這個匹配的花費為 c_AR + c_BP + c_CQ + c_DS = 4 + 2 + 3 + 2 = 11 而你的 sum {u_i} + sum {v_j} = -1 + -1 + -2 + 3 + 4 + 4 + 4 = 11 而這也是最少的花費。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 整理一下： X = {A, B, C, D, ...} 是所有多出一台車的地方 Y = {a, b, c, d, ...} 是所有少一台車的地方 |X| = |Y| = N (我們總是可以透過增加一些無用的據點，讓這個調件成立) c_ij (i \in X, j \in Y) 是從 i 運到 j 的花費， 那我們一開始令 u_i = 0, v_j = min {c_ij} 1. 考慮 c_ij - u_i - v_j 這張表中的 0 ，如果這些 0 可以形成一組完美匹配， 那現在的 sum {u_i} + sum {v_j} 就是答案，而那組完美匹配就是你要的運送方式， 否則就到步驟二 2. 找到最少的行或列，使所有的 0 都被這些行或列包含，令此行、列的集合為 Z 3. let e = min {c_ij - u_i - v_j | i \in (X\Z), j \in (Y\Z)} 4. for all x_i \in X ∩ Z, u_i <- u_i - e for all y_j \in Y \ Z, v_j <- v_j + e 回到步驟一 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 再來是比較痛苦的證明... 1. 從 u, v 變成 u', v' ，新的 u, v 還是滿足 u'_i + v'_j <= c_ij for all i, j 這個條件。 考慮 x_i \in X \ Z, y_j \in Y ∩ Z 因為 u_i, v_j 都沒變，所以不等式還是成立 考慮 x_i \in X ∩ Z, y_j \in Y \ Z u_i 少了 e ，v_j 多了 e ， u'_i + v'_j 不變，還是成立 考慮 x_i \in X ∩ Z, y_j \in Y ∩ Z u_i 少了 e ，v_j 不變，所以 u'_i + v'_j 變小，還是成立 考慮 x_i \in X \ Z, y_j \in Y \ Z u_i 不變，v_j 少 e ，u'_i + v'_j 變大了，不過 e = min {c_ij - u_i - v_j | i \in X\Z, j \in Y\Z} 也就是 e <= c_ij - u_i - v_j u'_i + v'_j = u_i + v_j - e <= u_i + v_j - (c_ij - u_i - v_j) u'_i + v'_j <= c_ij 還是成立 所以 u', v' 還是滿足這個性質 再來是停止條件，由前面我們可以知道 u, v 的和不會超過任何的運送方式， 而最便宜的運送方式恰好和 u, v 和的最大值相同，在我們的終止條件中， 是用 u, v 找到一組完美匹配 M ，這個匹配有 c(M) = sum {u} + sum {v} c(M) 代表 M 的花費 所以 M 是最少的花費， sum {u} + sum {v} 則是最大的 u, v 組合 所以，如果我們的操作可以達到終止條件，那我們得到的答案一定是對的， 再來的問題是我們可以達到終止條件嗎？ 答案當然是可以 首先， c_ij - u_i - v_j >= 0 for all i, j 而 e = min {c_ij - u_i - v_j | i \in X\Z, j \in Y\Z} Z 中的行或列已經包括了所有的 0 ，所以， e > 0 現在，假設 |X ∩ Z| = a, |Y ∩ Z| = b , |X| = |Y| = N, a + b = |Z| = z 那麼，有 a 個 u_i 會被減少，N - b 個 v_j 會被增加 sum {u'} + sum {v'} = sum {u} - (a * e) + sum {v} + (N - b) * e = sum {u} + sum {v} + (N - a - b) * e = sum {u} + sum {v} + (N - z) * e 因為 z < N (因為找不到完美匹配，如果 z = N ，一定找得到完美匹配) 所以 sum {u} + sum {v} 在每一次的操作都會增加，直到我們找到完美匹配為止 ================ 其實我們還可以證明在 N^2 次的操作內就會停止，不過有點麻煩，就略過了。 而且我也應該要給出 Z 的選擇流程，不過，人眼看還滿快的，也被我略過了。 ====================== 而在原本的問題呢，各地都多了數輛車或少了數輛車， 和我們簡化過的各地都只有一輛多的或少的車有點不同， 不過，我們可以把一個地方看成很多個小地方，他們都多或少一輛車， 比如 A 地，原本多了九輛，現在變成 A_1 ~ A_9 各多了一輛車， 而 P 地則變成 P_1 ~ P_5 ，各少一輛車，並且 A_i 到 P_j 的花費都是 60 元 這樣就和簡化過的問題一樣了。 如果，今天多了 x 輛車，少了 y 輛車，且 x > y ，代表有 x - y 輛車不用動 我們可以加入 x - y 個地點，他們都少了 1 輛車，並且， 不論從哪裡把車子運過來，花費都是 0 元，這樣又和簡化過的問題一樣了。 如果今天是 x < y ，我們可以反過來加入一些幽靈車，讓 x 和 y 變成一樣多。 大概就介紹到這邊吧 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 36.226.39.148