HDU1533回家之路：二分图的最大权匹配问题

在图论中，二分图的最大权匹配是一个重要的概念，特别是在解决实际问题时。本文将通过HDU1533《回家之路》这一具体题目来深入讲解如何利用匈牙利算法实现二分图的最大权匹配。

首先，我们需要理解二分图及其最大权匹配的基本概念。二分图是一种特殊的图，其顶点可以分为两个互不相交的集合，且每条边都连接两个不同集合中的顶点。最大权匹配是指在所有可能的匹配中选择一个，使得所选边的权重之和最大。

对于HDU1533题目，给定一个矩阵表示的地图，其中包含起点（'m'）和终点（'H'），目标是找到从每个起点到最近终点的最短路径，使得所有路径的总距离最小。这个问题可以通过构建一个二分图并求解最大权匹配来解决。

以下是具体的代码实现：

#include 
#include 
#include 

using namespace std;

const int MAXN = 100 + 10;
const int INF = (~0U >> 1);

char temp[MAXN][MAXN];
int c[MAXN][MAXN];
int lx[MAXN], ly[MAXN];
bool visx[MAXN], visy[MAXN];
int match[MAXN];
int row, col;
int numm, numh;

struct Node {
    int x, y;
} M[MAXN], H[MAXN];

int abs(int x) {
    return x <0 ? -x : x;
}

bool dfs(int u) {
    visx[u] = true;
    for (int i = 0; i         if (!visy[i] && lx[u] + ly[i] - c[u][i] == 0) {
            visy[i] = true;
            if (match[i] == -1 || dfs(match[i])) {
                match[i] = u;
                return true;
            }
        }
    }
    return false;
}

void solve() {
    memset(ly, 0, sizeof(ly));
    memset(match, -1, sizeof(match));
    for (int i = 0; i         lx[i] = c[i][0];
        for (int j = 1; j             if (c[i][j] > lx[i]) {
                lx[i] = c[i][j];
            }
        }
    }
    for (int i = 0; i         while (true) {
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
            if (dfs(i)) {
                break;
            }
            int inc = INF;
            for (int i = 0; i                 if (visx[i]) {
                    for (int j = 0; j                         if (!visy[j] && lx[i] + ly[j] - c[i][j]                             inc = lx[i] + ly[j] - c[i][j];
                        }
                    }
                }
            }
            for (int i = 0; i                 if (visx[i]) {
                    lx[i] -= inc;
                }
                if (visy[i]) {
                    ly[i] += inc;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i         ans += c[match[i]][i];
    }
    cout <<-ans <}

void input() {
    while (scanf("%d %d", &row, &col) && (row || col)) {
        numm = numh = 0;
        for (int i = 0; i             scanf("%s", temp[i]);
            for (int j = 0; j                 if (temp[i][j] == 'm') {
                    M[numm].x = i;
                    M[numm++].y = j;
                } else if (temp[i][j] == 'H') {
                    H[numh].x = i;
                    H[numh++].y = j;
                }
            }
        }
        for (int i = 0; i             for (int j = 0; j                 c[i][j] = -(abs(M[i].x - H[j].x) + abs(M[i].y - H[j].y));
            }
        }
        solve();
    }
}

int main() {
    input();
    return 0;
}

上述代码首先读取输入数据，构建二分图模型，然后使用匈牙利算法求解最大权匹配，最后输出结果。通过这种方式，我们可以有效地解决《回家之路》这类问题，同时也加深了对二分图最大权匹配算法的理解。