POJ 1548 Robots 最小路徑覆蓋 (二分圖最大匹配)

問題轉化

給定若干機器人坐標，機器人只能向右或向下移動。求最少需要多少條路徑覆蓋所有機器人（每條路徑從某機器人出發，沿右/下方向移動）。經典結論：最小路徑覆蓋 = 總節點數 - 最大匹配數。構建有向圖：若機器人 i 能到達 j（即 x_i ≤ x_j 且 y_i ≤ y_j），添加邊 i→j。求此二分圖的最大匹配。

算法流程

1. 讀入所有機器人坐標，編號 1..N。
2. 構建鄰接矩陣 line[i][j]：若 i 能到達 j 則為 1。
3. 匈牙利算法 (DFS 增廣路) 求最大匹配。
4. 答案 = N - 匹配數。

核心代碼 (C++)

const int MAXN = 900; // 30*30
int line[MAXN][MAXN], match[MAXN], vis[MAXN];
int N;

bool dfs(int u) {
    for (int v = 1; v <= N; ++v) if (line[u][v] && !vis[v]) {
        vis[v] = 1;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int maxMatching() {
    fill(match, match + N + 1, -1);
    int ans = 0;
    for (int u = 1; u <= N; ++u) {
        fill(vis, vis + N + 1, 0);
        if (dfs(u)) ++ans;
    }
    return ans;
}

輸入處理細節

多組測試數據，每組以 a b 開始，0 0 表示該組結束，-1 -1 表示全部結束。若 a=b=0 直接輸出 0。

複雜度

N ≤ 900，邊數 O(N²)。匈牙利算法 O(N·E) ≈ O(N³) 在此規模下可接受（實際測試通過）。