HDU Assignment：KM 算法變形——最大效益最小變動任務分配

問題描述

n 人 m 任務 (n ≤ m)。每人每任務有效益 w[i][j]。初始每人已有一任務。要求：在達到最大總效益前提下，盡量保持原任務分配不變（即改動任務數最少）。輸出：改動任務數、最大總效益。

建模：權值放大 + 偏移量

關鍵技巧：將所有效益乘以常數 K (取 K > n，如 K = n+m+5)，並給初始分配的任務 額外 +1。

新權值：W'[i][j] = w[i][j] * K + (init[i]==j ? 1 : 0)

為什麼有效？

• 最大化 Σ W' 等價於：先最大化 Σ w (因 K > n，任何效益差異 × K 都大於最多 n 個 +1 的總和)，再在最大效益解中最大化保持初始任務的數量（即 +1 的個數）
• 最終總效益 = Σ W' / K（整除）
• 改動數 = n - (Σ W' % K)（餘數即保持數）

KM 算法求最大權完全匹配

二分圖：左側 n 人，右側 m 任務。KM 步驟：

1. 初始可行頂標：Lx[i] = max_j W[i][j], Ly[j] = 0
2. 嘗試為每個左節點找增廣路（只走緊邊 Lx+Ly==W）
3. 找不到則修改頂標：d = min_{S,T} (Lx[i]+Ly[j]-W[i][j])，S 中 Lx-=d, T 中 Ly+=d
4. 重複直到完美匹配

核心代碼結構

const int K = 110; // > n+m
int W[55][55], Lx[55], Ly[55], link[55];
bool S[55], T[55];
int slack;

bool dfs(int u) {
    S[u] = true;
    for (int v=1; v<=m; ++v) if (!T[v]) {
        int gap = Lx[u] + Ly[v] - W[u][v];
        if (gap == 0) {
            T[v] = true;
            if (link[v]==-1 || dfs(link[v])) {
                link[v] = u; return true;
            }
        } else slack = min(slack, gap);
    }
    return false;
}

void update() {
    for (int i=1; i<=n; ++i) if (S[i]) Lx[i] -= slack;
    for (int j=1; j<=m; ++j) if (T[j]) Ly[j] += slack;
}

int main() {
    while (scanf("%d%d",&n,&m)==2) {
        for (i=1;i<=n;++i) for (j=1;j<=m;++j) {
            scanf("%d",&W[i][j]); W[i][j] *= K;
        }
        for (i=1;i<=n;++i) {
            int x; scanf("%d",&x);
            W[i][x]++;  // 初始任務 +1
        }
        KM(); // 求完美匹配
        int sum = 0;
        for (j=1;j<=m;++j) if (link[j]!=-1) sum += W[link[j]][j];
        int maxProfit = sum / K;
        int changed = n - sum % K;
        printf("%d %d\n", changed, maxProfit);
    }
}

複雜度

• KM：O(n²m) 或 O(n³)，n≤50 極快
• 權值放大技巧通用於「多目標優先級優化」問題