HDU 3523 Image Copy Detection：KM 算法求最小權完美匹配

題目轉化

給定 m 個長度為 n 的排列，求一個排列 t，使其與這 m 個排列的距離之和最小。距離定義為：dist = Σ|aᵢ - bᵢ|。

建模為二分圖匹配

• 左側節點：m 個排列的第 i 個位置 (1 ≤ i ≤ n)
• 右側節點：數值 1 到 n
• 邊權：w(i, j) = -Σ|A[k][i] - j| (k=1..m)
• 目標：求最大權完美匹配（原問題求最小，取反轉為最大）

匹配邊 i→j 表示數值 j 放在位置 i，一個完美匹配對應一個排列，最大權匹配對應最小距離和。

KM 算法核心實現

const int maxn = 100 + 10;
const int INF = 0x3f3f3f3f;

int nx, ny;                    // 兩邊點數
int g[maxn][maxn];             // 二分圖邊權
int linker[maxn], lx[maxn], ly[maxn];  // 匹配與頂標
int slack[maxn];
bool visx[maxn], visy[maxn];

bool DFS(int x) {
    visx[x] = true;
    for (int y = 1; y <= ny; y++) {
        if (visy[y]) continue;
        int tmp = lx[x] + ly[y] - g[x][y];
        if (tmp == 0) {  // 在相等子圖中
            visy[y] = true;
            if (linker[y] == -1 || DFS(linker[y])) {
                linker[y] = x;
                return true;
            }
        } else if (slack[y] > tmp) {
            slack[y] = tmp;  // 記錄最小 slack
        }
    }
    return false;
}

int KM() {
    memset(linker, -1, sizeof(linker));
    memset(ly, 0, sizeof(ly));
    
    // 初始化頂標：lx 為各行最大值
    for (int i = 1; i <= nx; i++) {
        lx[i] = -INF;
        for (int j = 1; j <= ny; j++)
            if (g[i][j] > lx[i]) lx[i] = g[i][j];
    }
    
    for (int x = 1; x <= nx; x++) {
        fill(slack + 1, slack + ny + 1, INF);
        while (true) {
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
            if (DFS(x)) break;
            
            // 修改頂標
            int d = INF;
            for (int i = 1; i <= ny; i++)
                if (!visy[i] && d > slack[i]) d = slack[i];
            
            for (int i = 1; i <= nx; i++)
                if (visx[i]) lx[i] -= d;
            for (int i = 1; i <= ny; i++) {
                if (visy[i]) ly[i] += d;
                else slack[i] -= d;
            }
        }
    }
    
    int res = 0;
    for (int i = 1; i <= ny; i++)
        if (linker[i] != -1) res += g[linker[i]][i];
    return res;
}

主程序邏輯

int a[maxn][maxn];
int main() {
    int T, n, m;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%d", &n, &m);
        nx = ny = n;
        
        // 讀入 m 個排列
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &a[i][j]);
        
        // 構建邊權矩陣
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                g[i][j] = 0;
                for (int k = 1; k <= m; k++)
                    g[i][j] -= abs(a[k][i] - j);
            }
        
        printf("Case #%d: %d\n", cas, -KM());
    }
    return 0;
}

關鍵點總結

• 下標從 1 開始，避免邊界錯誤
• 最小權匹配轉最大權：邊權取負，結果取負
• Slack 數組優化：避免每次重新計算所有非相等邊的差值
• 時間複雜度：O(n³)，n ≤ 100 完全可行