您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 1151 最小路徑覆蓋：有向無環圖的最大匹配轉化解法詳解

編輯：關於C++

在圖論競賽題中，「最小路徑覆蓋」是將有向無環圖（DAG）轉化為二分圖最大匹配的經典模型。本文以 HDU 1151 為例，完整推導「最小路徑覆蓋 = 頂點數 − 最大匹配數」的數學依據，並給出基於匈牙利演算法的 O(VE) 實作，適合 ACM/ICPC 選手與圖論愛好者深入研讀。

題目大意

給定一個無環有向圖（DAG），每條邊代表單向街道。若干傘兵可降落在任意路口，並順著邊方向移動。要求每個路口恰好被一位傘兵造訪一次，求最少需要多少傘兵。

等價於：用最少數量的不相交路徑覆蓋所有頂點，即 Minimum Path Cover in DAG。

核心定理與證明大綱

定理：對任意 DAG G = (V, E)，其最小路徑覆蓋數 P_min = |V| − M_max，其中 M_max 為對應二分圖的最大匹配數。

構造二分圖

將每個頂點 v ∈ V 拆分為左部 v_in 與右部 v_out。
對每條原圖有向邊 (u → v) ∈ E，在二分圖中加入無向邊 (u_out, v_in)。
此時二分圖的匹配邊集 M 對應原圖中「可合併為同一路徑」的頂點對：若 u_out — v_in ∈ M，表示 u 緊接在 v 之前，兩者屬於同一路徑。

從匹配到路徑覆蓋

匹配邊數 |M| 條 ⇒ 可合併 |M| 對頂點 ⇒ 路徑條數減少 |M| 條。
初始每頂點自成一路徑（共 |V| 條），合併後剩 |V| − |M| 條。
最大匹配使合併數最多，故路徑數最少。

演算法流程

讀入測資組數 T。
對每組：讀 n（頂點數 ≤ 120）、m（邊數）。
建立鄰接矩陣 g[u][v]（1-based）。
跑匈牙利演算法求最大匹配 ans。
輸出 n - ans。

完整 C++ 實作（含註解）

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 125;          // 題目上限 120，稍留餘量
int n, m;
bool g[MAXN][MAXN];            // 鄰接矩陣：g[u][v] = true 表示 u→v
int match[MAXN];               // match[v] = u 表示 v_in 與 u_out 配對
bool vis[MAXN];                // DFS 訪問標記

// 嘗試為左部頂點 u 尋找增廣路徑
bool dfs(int u) {
    for (int v = 1; v <= n; ++v) {
        if (g[u][v] && !vis[v]) {
            vis[v] = true;
            if (match[v] == 0 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

// 匈牙利演算法主流程
int hungarian() {
    memset(match, 0, sizeof(match));
    int ans = 0;
    for (int u = 1; u <= n; ++u) {
        memset(vis, 0, sizeof(vis));
        if (dfs(u)) ++ans;
    }
    return ans;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        memset(g, 0, sizeof(g));
        for (int i = 0; i < m; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            g[u][v] = true;            // 有向邊 u → v
        }
        int maxMatch = hungarian();
        printf("%d\n", n - maxMatch);  // 最小路徑覆蓋
    }
    return 0;
}