先把题目简化： 有 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