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