2012-01-26 1/26 PKU Algorithm PKU 3375 Network Connection ネットワークインタフェースと、パソコンをつなぐ。それぞれは数直線上にある。すべてのパソコンをいずれかのインタフェースにつなぎたい。複数のパソコンにつながれるインタフェースがあってはいけない。ケーブル長の和を最小化せよ。O(MN)のDPを、適当に改善してO(N^2)にする