BZOJ 1108 [POI2007] 天然氣管道 Gaz - 曼哈頓距離最小權完備匹配

這是一道看似複雜、實則極其優雅的數學建模題。給定平面上 n 個黑點和 n 個白點，黑點只能與其右下方的白點匹配，代價為曼哈頓距離，求最小權值完備匹配。

核心洞察：代價函數的可分解性

曼哈頓距離 |x_b - x_w| + |y_b - y_w|，在「黑點在白點左上」的約束下（即 x_b ≤ x_w, y_b ≥ y_w），絕對值可直接展開：

cost = (x_w - x_b) + (y_b - y_w)
     = (y_b - y_w) + (x_w - x_b)

對所有匹配對求和，總代價為：

Σ(y_black) - Σ(y_white) + Σ(x_white) - Σ(x_black)

驚人地發現：總代價與具體匹配方式無關！ 只要滿足約束條件（黑點在白點左上），任意完備匹配的總代價都是定值。因此，問題轉化為：驗證是否存在合法匹配，若存在則直接按上式計算答案。

算法流程

1. 讀入 n。
2. 累加所有黑點的 y，減去 x（即 ans += y - x）。
3. 累加所有白點的 x，減去 y（即 ans += x - y）。
4. 輸出 ans。

時間複雜度 O(n)，空間複雜度 O(1)。

代碼實現

#include <cstdio>
#include <iostream>
using namespace std;

int main() {
    int n;
    long long ans = 0;
    while (cin >> n) {
        ans = 0;
        for (int i = 0, x, y; i < n; i++) {
            scanf("%d%d", &x, &y);
            ans += y; ans -= x; // 黑點
        }
        for (int i = 0, x, y; i < n; i++) {
            scanf("%d%d", &x, &y);
            ans += x; ans -= y; // 白點
        }
        cout << ans << endl;
    }
    return 0;
}

總結

這道題是「化繁為簡」的典範：通過數學推導發現匹配的具體結構不影響目標函數值，將圖論匹配問題轉化為簡單的坐標累加。解題關鍵在於敏銳地發現約束條件下曼哈頓距離的線性可分解性。