您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

POJ 2195 Going Home - KM 算法最小權完美匹配

編輯：C++ 入門

題目模型

網格地圖，n 個小人 (m) 和 n 個房子 (H)。曼哈頓距離為代價。每人進一房，求最小總代價。二分圖最小權完美匹配。

KM 算法 (Kuhn-Munkres)

將最小權轉為最大權：weight = -distance
頂標 lx[i], ly[j]，可行頂標：lx[i] + ly[j] ≥ w[i][j]
相等子圖中找完美匹配，失敗則調整頂標 (減最小 slack)
複雜度 O(n^3)，n ≤ 100 完全足夠

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2500, INF = 0x3f3f3f3f;

int n, m, nx, ny;
char mp[120][120];
struct Pt { int x, y; } man[MAXN], house[MAXN];
int g[MAXN][MAXN], linker[MAXN], lx[MAXN], ly[MAXN], slack[MAXN];
bool vx[MAXN], vy[MAXN];

bool dfs(int u) {
    vx[u] = true;
    for (int v = 0; v < ny; v++) if (!vy[v]) {
        int d = lx[u] + ly[v] - g[u][v];
        if (d == 0) {
            vy[v] = true;
            if (linker[v] == -1 || dfs(linker[v])) {
                linker[v] = u; return true;
            }
        } else slack[v] = min(slack[v], d);
    }
    return false;
}

int KM() {
    fill(linker, linker+ny, -1);
    fill(ly, ly+ny, 0);
    for (int i = 0; i < nx; i++) {
        lx[i] = -INF;
        for (int j = 0; j < ny; j++) lx[i] = max(lx[i], g[i][j]);
    }
    for (int u = 0; u < nx; u++) {
        fill(slack, slack+ny, INF);
        while (true) {
            fill(vx, vx+nx, false);
            fill(vy, vy+ny, false);
            if (dfs(u)) break;
            int d = INF;
            for (int i = 0; i < ny; i++) if (!vy[i]) d = min(d, slack[i]);
            for (int i = 0; i < nx; i++) if (vx[i]) lx[i] -= d;
            for (int i = 0; i < ny; i++) if (vy[i]) ly[i] += d; else slack[i] -= d;
        }
    }
    int res = 0;
    for (int i = 0; i < ny; i++) if (linker[i] != -1) res += g[linker[i]][i];
    return res;
}

int main() {
    while (scanf("%d%d", &n, &m) == 2 && (n||m)) {
        nx = ny = 0;
        for (int i = 0; i < n; i++) scanf("%s", mp[i]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (mp[i][j] == 'H') house[ny++] = {i,j};
                else if (mp[i][j] == 'm') man[nx++] = {i,j};
        for (int i = 0; i < nx; i++)
            for (int j = 0; j < ny; j++)
                g[i][j] = -(abs(man[i].x-house[j].x) + abs(man[i].y-house[j].y));
        printf("%d\n", -KM());
    }
    return 0;
}