POJ 1325：二分圖匹配解析——機器模式切換的最小重啟次數

問題背景

有兩台機器，分別擁有 n 種和 m 種模式（均從 0 開始編號）。共有 k 個任務，每個任務可以由第一台機器的 x 模式或第二台機器的 y 模式完成。每當機器切換模式時都需要重啟，重啟後初始模式為 0。目標是找出完成所有任務所需的最少重啟次數。

核心思路：最小點覆蓋與最大匹配

將每個任務視為一條邊，連接第一台機器的模式 x 和第二台機器的模式 y。兩台機器的模式自然形成二分圖的兩個頂點集合。問題轉化為：在這個二分圖中選擇最少的頂點（模式），使得每條邊（任務）至少有一個端點被選中——這正是最小點覆蓋問題。

根據 Kőnig 定理，二分圖的最小點覆蓋數等於最大匹配數。因此，我們只需求出該二分圖的最大匹配數即可得到答案。

關鍵細節：模式 0 的特殊處理

重啟後機器自動處於模式 0，無需額外重啟。因此，若任務涉及模式 0（即 b==0 或 c==0），該任務不需消耗重啟次數，構建圖時可直接忽略這類邊。

算法實現（匈牙利算法 / DFS 增廣路）

#include <cstdio>
#include <cstring>

const int MAXN = 105;
int n, m, k;
int g[MAXN][MAXN];
int link[MAXN];
bool vis[MAXN];

bool dfs(int u) {
    for (int v = 0; v < m; ++v) {
        if (g[u][v] && !vis[v]) {
            vis[v] = true;
            if (link[v] == -1 || dfs(link[v])) {
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    while (scanf("%d", &n) == 1 && n) {
        memset(g, 0, sizeof(g));
        scanf("%d%d", &m, &k);
        for (int i = 0; i < k; ++i) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            if (b == 0 || c == 0) continue; // 模式 0 無需重啟
            g[b][c] = 1;
        }

        int match = 0;
        memset(link, -1, sizeof(link));
        for (int u = 0; u < n; ++u) {
            memset(vis, 0, sizeof(vis));
            if (dfs(u)) ++match;
        }
        printf("%d\n", match); // 最大匹配數即為最少重啟次數
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n * k)，其中 n ≤ 100，k ≤ 10000，完全可接受。
• 空間複雜度：O(n * m) 用於存儲鄰接矩陣。

總結

本題巧妙地將調度問題轉化為經典的二分圖最大匹配模型，利用「重啟後初始模式為 0」這一條件簡化圖的構建。掌握「最小點覆蓋 = 最大匹配」的轉化技巧，是解決此類問題的關鍵。