最大流增广路(KM算法) HDOJ 1533 Going Home

题目传送门

 /*
最小费用流:KM算法是求最大流,只要w = -w就可以了,很经典的方法
*/
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std; const int MAXN = 1e2 + ;
const int INF = 0x3f3f3f3f;
int x[MAXN], y[MAXN];
int w[MAXN][MAXN];
int visx[MAXN], visy[MAXN];
int ly[MAXN];
int mx[MAXN], my[MAXN];
int hx[MAXN], hy[MAXN];
char maze[MAXN][MAXN];
int n, m, un, vn, d; bool DFS(int u) {
visx[u] = true;
for (int i=; i<=un; ++i) {
if (!visy[i] && x[u] + y[i] == w[u][i]) {
visy[i] = true;
if (ly[i] == - || DFS (ly[i])) {
ly[i] = u; return true;
}
}
else if (x[u] + y[i] > w[u][i]) d = min (d, x[u] + y[i] - w[u][i]);
}
return false;
} int KM(void) {
for (int i=; i<=un; ++i) {
x[i] = -INF;
for (int j=; j<=vn; ++j) {
x[i] = max (x[i], w[i][j]);
}
} memset (ly, -, sizeof (ly));
memset (y, , sizeof (y));
for (int i=; i<=un; ++i) {
while (true) {
memset (visx, false, sizeof (visx));
memset (visy, false, sizeof (visy));
d = INF;
if (DFS (i)) break;
for (int i=; i<=un; ++i) {
if (visx[i]) x[i] -= d;
}
for (int j=; j<=vn; ++j) {
if (visy[j]) y[j] += d;
}
}
} int res = ;
for (int i=; i<=un; ++i) {
res += x[i] + y[i];
} return res;
} int main(void) { //HDOJ 1533 Going Home
//freopen ("HDOJ_1533.in", "r", stdin); while (scanf ("%d%d", &n, &m) == ) {
if (!n && !m) break;
for (int i=; i<=n; ++i) {
scanf ("%s", maze[i] + );
}
un = vn = ;
for (int i=; i<=n; ++i) {
for (int j=; j<=m; ++j) {
if (maze[i][j] == 'm') mx[++un] = i, my[un] = j;
else if (maze[i][j] == 'H') hx[++vn] = i, hy[vn] = j;
}
}
for (int i=; i<=un; ++i) {
for (int j=; j<=vn; ++j) {
w[i][j] = -(abs (mx[i] - hx[j]) + abs (my[i] - hy[j]));
}
}
printf ("%d\n", -KM ());
} return ;
}
上一篇:MS SQL自定义函数IsNumeric


下一篇:最大流增广路(KM算法) HDOJ 2255 奔小康赚大钱