POJ 2195: Going Home

http://poj.org/problem?id=2195

これも最大マッチングに毛を生やした程度。
最小コスト完全マッチング問題とか言われるやつ。

namespace MCF(Minimum Cost Flow)を使っているのだがMFと書きがちなので注意。

nt H, M;
int HX[MAX_N], HY[MAX_N];
int MX[MAX_N], MY[MAX_N];

char s[MAX_N];

int main() {
	while(true) {
		scanf("%d%d", &X, &Y);
		if(X == 0 && Y == 0) break;
		H = 0; M = 0;
		rep(i, 0, X) {
			scanf("%s", s);
			rep(j, 0, Y) {
				if(s[j] == 'm') {
					MX[M] = i;
					MY[M] = j; M++;
				}
				else if(s[j] == 'H') {
					HX[H] = i;
					HY[H] = j; H++;
				}
			}
		}
		MCF::init(H + M + 2);
		int s = H + M, t = H + M + 1;
		rep(i, 0, H) {
			rep(j, 0, M) {
				int dist = abs(HX[i] - MX[j]) + abs(HY[i] - MY[j]);
				MCF::add_edge(i, j + H, 1, dist);
			}
		}
		rep(i, 0, H) MCF::add_edge(s, i, 1, 0);
		rep(i, 0, M) MCF::add_edge(i + H, t, 1, 0);
		printf("%d\n", MCF::get(s, t, H));
	}
	return 0;
}

最小費用流はアルゴリズムが難しい(ポテンシャルのところとか)けど使うだけならそこまで苦労しないのかな。