HDU 1350 Taxi Cab Scheme：二分圖最大匹配求最少出租車數

問題建模

每個預約訂單為一個節點。若司機完成訂單 i 後能趕上訂單 j（到達時間 + 1 分鐘 ≤ j 出發時間），連有向邊 i → j。
目標：用**最少路徑覆蓋所有節點** → 等價於 **最小路徑覆蓋 = 節點數 - 最大匹配數**（DAG 上）。

關鍵細節

• 曼哈頓距離：|x1-x2| + |y1-y2| 分鐘。
• 換單需間隔 ≥ 1 分鐘，故到達時間 + 1 ≤ 下一單出發時間。
• 訂單已按出發時間升序，圖無環（DAG）。
• M < 500，鄰接矩陣/表均可，匈牙利算法 O(VE) 足夠。

完整代碼

#include 
using namespace std;

struct Order {
    int st, et; // 開始/結束時間（分鐘）
    int sx, sy, ex, ey;
} ord[510];

int n;
bool g[510][510];
int match[510];
bool vis[510];

bool dfs(int u) {
    for (int v = 0; v < n; ++v) if (g[u][v] && !vis[v]) {
        vis[v] = true;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int maxMatching() {
    memset(match, -1, sizeof(match));
    int ans = 0;
    for (int u = 0; u < n; ++u) {
        memset(vis, 0, sizeof(vis));
        if (dfs(u)) ++ans;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            string tm; cin >> tm;
            int hh = stoi(tm.substr(0,2)), mm = stoi(tm.substr(3,2));
            int a,b,c,d; cin >> a >> b >> c >> d;
            ord[i].st = hh*60 + mm;
            ord[i].sx = a; ord[i].sy = b;
            ord[i].ex = c; ord[i].ey = d;
            ord[i].et = ord[i].st + abs(a-c) + abs(b-d);
        }
        memset(g, 0, sizeof(g));
        for (int i = 0; i < n; ++i)
            for (int j = i+1; j < n; ++j)
                if (ord[i].et + 1 <= ord[j].st)
                    g[i][j] = true;
        int match = maxMatching();
        cout << n - match << "\n";
    }
    return 0;
}

複雜度

• 建圖：O(n²)。
• 匈牙利：O(n × E) ≤ O(n³)，n=500 內極快。

小結

經典「區間調度 + 最小路徑覆蓋」轉二分圖最大匹配。關鍵在正確計算可達條件（含 1 分鐘緩衝）並利用 DAG 性質套用定理。