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

問題描述

給定一個有向無環圖（DAG），代表城鎮的單向街道和十字路口。傘兵可從任意路口著陸，並沿街道方向移動。每個路口只能被一名傘兵訪問。求訪問所有路口所需的最少傘兵數。

核心模型：最小路徑覆蓋

在 DAG 中，最小路徑覆蓋 = 頂點數 - 最大匹配數。將原圖每個頂點拆分為左右兩部分（U 集合和 V 集合），原有向邊 u→v 轉化為無向邊 u(U)-v(V)。在這個二分圖中求最大匹配，匹配邊代表路徑中的連接關係。未被匹配的左側頂點即為路徑起點，其數量即為最小路徑覆蓋數。

算法流程

1. 讀入頂點數 n、邊數 m。
2. 建立鄰接矩陣 ma[u][v] 表示有向邊。
3. 匈牙利算法（DFS 版）求二分圖最大匹配：
   - line[v] 記錄右側頂點 v 匹配的左側頂點。
   - 對每個左側頂點 u，重置訪問標記 vis，嘗試尋找增廣路徑。
   - DFS 過程中若找到未匹配的右頂點或能騰出匹配位置，則更新匹配關係。
4. 答案 = n - 最大匹配數。

完整代碼

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <math.h>
#define init(a) memset(a, 0, sizeof(a))
#define PI acos(-1.0)
using namespace std;
const int maxn = 310;
int ma[maxn][maxn];
int line[maxn];
bool vis[maxn];
int n, m;

int DFS(int u) {
    for (int v = 1; v <= n; v++) {
        if (!vis[v] && ma[u][v] == 1) {
            vis[v] = true;
            if (line[v] == -1 || DFS(line[v])) {
                line[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int K_M() {
    int ans = 0;
    memset(line, -1, sizeof(line));
    for (int i = 1; i <= n; i++) {
        init(vis);
        ans += DFS(i);
    }
    return ans;
}

int main() {
    int x, y, t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        init(ma);
        for (int i = 1; i <= m; i++) {
            scanf("%d%d", &x, &y);
            ma[x][y] = 1;
        }
        int ans = K_M();
        printf("%d\n", n - ans);
    }
    return 0;
}

關鍵點解析

• 圖的轉化：原 DAG 的最小路徑覆蓋等價於二分圖的最大匹配補集。每條匹配邊將兩條路徑合併，減少一條路徑。
• 匈牙利算法適用性：n ≤ 120，鄰接矩陣 + DFS 完全足夠，無需 Hopcroft-Karp。
• 無環保證：題目給定無環，否則最小路徑覆蓋為 NP-hard。

複雜度

• 時間：O(n * m) ≈ O(n^3) 在稠密圖下，n=120 時極快。
• 空間：O(n^2) 鄰接矩陣。

經典例題輸入輸出

Sample Input:
2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

Sample Output:
2
1

第一個案例：4個頂點，3條邊 3→4, 1→3, 2→3。最大匹配為 2（如 1-3, 2-4 或 1-3, 3-4），答案 4-2=2。
第二個案例：3個頂點，邊 1→3, 1→2, 2→3。最大匹配 2（1-2, 2-3），答案 3-2=1。