HDU 1151 Air Raid：最小路徑覆蓋 = |V| - 最大匹配（DAG 空襲路徑規劃）

問題描述

有向無環圖 (DAG) 表示城市道路。飛機從起點飛到終點，每條路徑可覆蓋沿途城市。求最少飛機數覆蓋所有城市（每城市至少被一條路徑經過）。

最小路徑覆蓋定理

DAG 中**最小不相交路徑覆蓋數** = |V| - 最大匹配數。
構造二分圖：
- 左部 U、右部 V 均為原圖頂點集合。
- 原圖邊 u→v → 二分圖邊 u(U) → v(V)。
最大匹配中每條匹配邊代表將兩條路徑合併（u 接 v）。

匈牙利算法求最大匹配

int n; vector G[MAXN];
int match[MAXN]; bool vis[MAXN];

bool dfs(int u) {
    for (int v : G[u]) if (!vis[v]) {
        vis[v] = true;
        if (match[v]==-1 || dfs(match[v])) {
            match[v] = u; return true;
        }
    }
    return false;
}

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

關鍵注意點

• 圖必須是 **DAG**，否則定理不成立。
• 匹配邊方向：左部→右部，對應原圖邊方向。
• 孤立點無匹配邊，各自形成長度 1 的路徑。
• 輸入可能有多組測試，直到 EOF。

複雜度

O(V * E)，V ≤ 100，E ≤ V^2，極快。

擴展：最小路徑覆蓋輸出具體路徑

從未被匹配為右端點的頂點出發，沿匹配邊反向/正向追蹤構造路徑。