Maximum-Cup 2013 F - 3人の騎士と1匹の犬

• 問題
• AC

魔力$0$の保有者はいかなる場合も不要なので最初に取り除き、$M$を$1$以上の魔力の保有者の総数としておく。

$N \ge M$のケースは簡単で、マンハッタン距離をコストにして、$M$個の騎士・魔力保有者のペアを作る最小重みマッチングを求めればよい。

$N < M$のケースが難しかった。魔力保有者をあらかじめ魔力の降順にソートしておいて、上位$N$人の魔力保有者とのマッチングを考えればよいのだけれど、$\operatorname{MAGIC}_N$とちょうど同じ魔力を持つ者が複数人いたときに誰を選ぶかが問題になる。端的には、次のようにすればよい: （$s, t$をフローの始点、終点とする）

• $s$から各騎士に、容量$1$、コスト$0$の辺を張る。
• 各魔力保有者から$t$に、容量$1$、コスト$0$の辺を張る。
• 各騎士から$\operatorname{MAGIC}_N$より大きな魔力の保有者に、容量$1$、コストがマンハッタン距離$-20000$の辺を張る。
• 各騎士からちょうど$\operatorname{MAGIC}_N$の魔力の保有者に、容量$1$、コストがマンハッタン距離の辺を張る。

$\operatorname{MAGIC}_N$より大きな魔力の保有者が必ずマッチングに含まれるようにしたいので、$-20000$の補正を入れている。あとは流量$N$の最小コストを求めて、$20000 \times \operatorname{MAGIC}_Nより大きな魔力の保有者の数$を足して戻せば答えになっている。