この問題は、 Gomory-Hu のアルゴリズムを使うことで解くことができます。
まず、頂点集合の集合 S を {{1,2,…,N}} で初期化します。
集合 S に対して、次の操作を繰り返します。
- 頂点集合 S からある集合を取り、 s とする。
- s の要素数が 1 以下なら捨てる。
- s から適当な二つの頂点を取り、問題のネットワーク上で最大カットを求める。(このとき、カットの容量を覚えておく。)
- s に属する頂点をカットによって二つに分割し、両方を S に追加する。
この問題の答えは、 3. で求めたカットの容量の最大値になります。
操作を繰り返す回数は O(N) 回なので、最大カットを容量スケーリング Edmonds-Karp O(M2log∑iCi) で求めることで、この問題を O(NM2log∑iCi) で解くことができました。
テストケース募集中
2022/05/29 現在、この問題にはランダムケースしかありません。
遅い解法を落とせるハックケースなど、募集中です。
連絡は @0x3b800001 まで。