HDU 1151 Air Raid：有向無環圖最小路徑覆蓋解析

問題轉化

城鎮有 m 個路口、n 條單向路（無環）。傘兵只能順路方向巡查，求覆蓋所有路口的最少傘兵數。
這等價於求有向無環圖（DAG）的最小路徑覆蓋。

核心定理

DAG 最小路徑覆蓋 = 頂點數 - 最大匹配數

將原圖每個頂點拆分為左右兩部分（U、V），原有邊 u→v 轉為二分圖邊 U_u → V_v。最大匹配即為能串聯的路徑段數，剩餘未匹配頂點即為路徑起點數。

算法實現（匈牙利算法）

const int MAX = 121;
int link[MAX];       // V部匹配的U頂點
bool map[MAX][MAX];  // 二分圖鄰接矩陣
bool useif[MAX];     // DFS訪問標記

bool can(int u) {    // 尋找增廣路徑
    for (int v=1; v<=n; v++)
        if (!useif[v] && map[u][v]) {
            useif[v] = true;
            if (link[v] == -1 || can(link[v])) {
                link[v] = u;
                return true;
            }
        }
    return false;
}

int maxMatch() {
    int ans = 0;
    memset(link, -1, sizeof(link));
    for (int u=1; u<=n; u++) {
        memset(useif, 0, sizeof(useif));
        if (can(u)) ans++;
    }
    return ans;
}

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

複雜度分析

• 時間：O(V × E)，V≤120，E≤V²，完全滿足題目限制
• 空間：O(V²) 鄰接矩陣

關鍵點：正確建模二分圖、匈牙利算法模板應用、理解「頂點數 - 最大匹配」的圖論意義。