komiyam https://blog.hatena.ne.jp/komiyam/ komiyamの日記 https://komiyam.hatenadiary.org/ TopCoder keyword 2部グラフ マッチング C++ 概要 N( まず、移動距離を決めないとどうしようもないので移動距離については全探索する(A_0とB_iの差を見れば良い)。移動距離さえ決めてしまえば2部グラフが構成できるので、あとは最大マッチングがNとなる個数を足し合わせるだけ。 さて、SuperCon2010のときの経験から、2部グラフの完全マッチングの個数なんて普通にやっても上手くいかないことは既に知っている。平面グラフの最大マッチングの個数は多項式時間で求められる様だけど、そんなライブラリはないし、平面グラフになるかわからないし、そもそもMidiumの問題でそれはないだろう。ということはグ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkomiyam.hatenadiary.org%2Fentry%2F20110201%2F1296574313" title="SRM496 500pt:OneDimensionalBalls - komiyamの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2011-02-01 00:31:53 rich https://komiyam.hatenadiary.org/entry/20110201/1296574313 1.0 100%