POJ 2594 Treasure Exploration：最小路徑覆蓋與最大匹配

問題背景

給定一個有向圖，求最小路徑覆蓋數。根據圖論定理，DAG 的最小路徑覆蓋數等於節點數減去最大匹配數。本題需先用 Floyd-Warshall 算法求傳遞閉包，再構造二分圖跑最大匹配（匈牙利算法）。

算法流程

1. 讀入節點數 n、邊數 m。
2. 建立鄰接矩陣 line[u][v]，跑 Floyd 算法得到傳遞閉包：line[j][k] = line[j][k] || (line[j][i] && line[i][k])。
3. 構造二分圖：左部與右部均為原圖節點，若 line[u][v] == 1 則連邊 u -> v。
4. 使用 DFS 基於匈牙利算法求最大匹配 MaxMatch。
5. 答案為 n - MaxMatch()。

關鍵代碼片段

void floyd() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                if (line[j][i] && line[i][k])
                    line[j][k] = 1;
}

bool get_path(int u) {
    for (int i = 1; i <= n; i++)
        if (line[u][i] && !used[i]) {
            used[i] = 1;
            if (mac[i] == -1 || get_path(mac[i])) {
                mac[i] = u;
                return true;
            }
        }
    return false;
}

int MaxMatch() {
    int num = 0;
    memset(mac, -1, sizeof(mac));
    for (int i = 1; i <= n; i++) {
        memset(used, 0, sizeof(used));
        if (get_path(i)) num++;
    }
    return num;
}

注意事項

• 輸入包含多組測試數據，以 n=0, m=0 結束。
• 圖中可能存在自環或重邊，Floyd 過程會自動處理傳遞關係。
• 時間複雜度：Floyd O(n^3)，匈牙利 O(n*m)，n ≤ 500 可接受。