HDU 1150 Machine Schedule：二分圖最小點覆蓋 = 最大匹配（機器模式切換最小化）

問題建模

兩台機器 A、B，N 個任務。任務 i 在 A 需模式 x_i，在 B 需模式 y_i。機器切換模式需重啟（代價 1）。任務在機器上順序任意。安排每個任務到 A 或 B，並決定處理順序，使總重啟次數最小。

關鍵轉化

若任務 i 分給 A，則 A 需設置模式 x_i；分給 B 則 B 需 y_i。
同一機器上，相同模式的任務可連續處理，**無需重啟**。
問題等價於：選擇一組模式（A 的某些模式 + B 的某些模式），使得每個任務至少被覆蓋（即 x_i 在 A 選中 或 y_i 在 B 選中）。
這就是**二分圖最小點覆蓋**！

二分圖構建

• 左部：機器 A 的所有模式（編號 1..M）。
• 右部：機器 B 的所有模式（編號 1..M）。
• 任務 i → 邊 (x_i, y_i)。
• 初始模式 0 無代價，**不加入圖中**（或視為已選中）。

Kőnig 定理：最小點覆蓋 = 最大匹配

用匈牙利算法（DFS 增廣路）求最大匹配數，即為答案。

匈牙利算法模板

int n, m; // 左右部大小
vector G[MAXN];
int match[MAXN]; bool vis[MAXN];

bool dfs(int u) {
    for (int v : G[u]) if (!vis[v]) {
        vis[v] = true;
        if (match[v]==-1 || dfs(match[v])) {
            match[v] = u; return true;
        }
    }
    return false;
}

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

完整流程

while (cin >> N) {
    if (N==0) break;
    cin >> M >> K; // M: 模式數, K: 任務數
    // 初始化圖
    for (int i=0;i>x>>y;
        if (x!=0 && y!=0) G[x].push_back(y); // 忽略模式 0
    }
    cout << maxMatching() << "\n";
}

複雜度

O(N * E)，N,M ≤ 100，E ≤ N，極快。