HDU 1151 Air Raid：最小路徑覆蓋與二分圖最大匹配

HDU 1151 是經典的「最小路徑覆蓋」問題，通過建模轉化為二分圖最大匹配求解。本文詳細解析建模思路、算法原理與 AC 代碼。

問題描述

• 有向無環圖（DAG），m 個頂點（路口），n 條有向邊（單向路）
• 需派遣最少傘兵，每人沿有向邊移動，覆蓋所有頂點
• 求最小路徑覆蓋數

核心定理

有向無環圖的最小路徑覆蓋 = 頂點數 - 最大匹配數

將原圖每個頂點 u 拆分為左部 u_in 和右部 u_out，原有向邊 u→v 轉為二分圖邊 u_in — v_out。最大匹配對應的路徑合併操作，未被匹配的左部頂點即為路徑起點。

算法流程

1. 輸入測試用例數 t
2. 每組讀取 m（頂點數）、n（邊數）
3. 建立鄰接矩陣 map[u][v] 表示二分圖邊
4. 匈牙利算法求最大匹配
5. 答案 = m - maxMatch()

匈牙利算法核心代碼

bool can(int u) {                    // 從左部頂點 u 尋找增廣路徑
    for (int v = 1; v <= m; v++) {
        if (!vis[v] && map[u][v]) {
            vis[v] = true;
            if (link[v] == -1 || can(link[v])) {
                link[v] = u;         // 匹配成功
                return true;
            }
        }
    }
    return false;
}

int maxMatch() {
    memset(link, -1, sizeof(link));
    int match = 0;
    for (int u = 1; u <= m; u++) {
        memset(vis, 0, sizeof(vis));
        if (can(u)) match++;
    }
    return match;
}

完整 AC 代碼

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

const int MAX = 121;
int m, n, t;
bool map[MAX][MAX];
int link[MAX];
bool vis[MAX];

bool can(int u) {
    for (int v = 1; v <= m; v++) {
        if (!vis[v] && map[u][v]) {
            vis[v] = true;
            if (link[v] == -1 || can(link[v])) {
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

int maxMatch() {
    memset(link, -1, sizeof(link));
    int match = 0;
    for (int u = 1; u <= m; u++) {
        memset(vis, 0, sizeof(vis));
        if (can(u)) match++;
    }
    return match;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    while (t--) {
        cin >> m >> n;
        memset(map, 0, sizeof(map));
        for (int i = 0; i < n; i++) {
            int a, b;
            cin >> a >> b;
            map[a][b] = true;
        }
        cout << m - maxMatch() << '\n';
    }
    return 0;
}

複雜度分析

• 時間：O(m × n) —— 每個左部頂點做一次 DFS，邊數為 n
• 空間：O(m²) —— 鄰接矩陣，m ≤ 100 完全可接受

關鍵點總結

延伸思考

最小路徑覆蓋還有「不相交路徑覆蓋」（頂點不重複）與「可相交路徑覆蓋」之分。本題為後者，即允許路徑共享頂點，恰好對應定理。若要求頂點不相交，則需網絡流建模（最小費用最大流）。

結語

HDU 1151 是圖論建模的經典入門題。掌握「最小路徑覆蓋 = 頂點數 - 最大匹配」這一轉化，配合匈牙利算法模板，即可秒殺同類問題。建議輔以《算法導論》第 26 章、胡凡《圖論及其應用》深入理解證明細節。