URAL 1949 最佳影片：二分匹配求字典序最小解

URAL 1949 最佳影片：二分匹配求字典序最小解

n 部電影，k 名學生。每部電影有開始/結束時間、女演員數。學生看電影需滿足：時間不衝突（下一部開始 ≥ 上一部結束），女演員數不減。求最多能看多少部電影，輸出 0/1 序列表示選擇方案，多解取字典序最小。

建模：最小路徑覆蓋 = 最大匹配

• 每部電影拆為左右兩個節點 X_i, Y_i。
• 若電影 i 可接在 j 後（b_j ≤ a_i 且 c_j ≤ c_i），加邊 X_j → Y_i。
• 最大匹配數 = 最小路徑覆蓋數 = 最少學生數。若 ≤ k，則可行。

字典序最小的貪心構造

按電影編號 1..n 處理：

1. 嘗試加入電影 i，構建當前圖的匹配。
2. 若匹配數增加（即成功納入現有路徑），保留該電影（輸出 1）。
3. 否則，若仍有空閒學生（當前路徑數 < k），強制作為新路徑起點（輸出 1）。
4. 否則捨棄該電影（輸出 0）。

此貪心保證字典序最小，因為優先保留編號小的電影。

代碼框架

bool ok(int x, int y) { // y 可接在 x 後
    return b[x] <= a[y] && c[x] <= c[y];
}
int solve() { // 當前圖的最大匹配
    memset(lef, -1, sizeof lef);
    int ans = 0;
    for (int i = 1; i <= n; ++i) if (!del[i]) {
        memset(T, 0, sizeof T);
        if (match(i)) ++ans;
    }
    return ans;
}
int main() {
    while (~scanf("%d%d", &n, &k)) {
        // 讀入、構建邊
        int delnum = 0;
        for (int i = 1; i <= n; ++i) {
            // 加入邊 i→j, j k) { del[i] = 1; delnum++; ok_add = false; }
            printf("%d", ok_add);
        }
        puts("");
    }
}