この問題は、 Gomory-Hu のアルゴリズムを使うことで解くことができます。

まず、頂点集合の集合 SS{{1,2,,N}}\{\{ 1, 2, \ldots, N \}\} で初期化します。

集合 SS に対して、次の操作を繰り返します。

  1. 頂点集合 SS からある集合を取り、 ss とする。
  2. ss の要素数が 11 以下なら捨てる。
  3. ss から適当な二つの頂点を取り、問題のネットワーク上で最大カットを求める。(このとき、カットの容量を覚えておく。)
  4. ss に属する頂点をカットによって二つに分割し、両方を SS に追加する。

この問題の答えは、 3. で求めたカットの容量の最大値になります。

操作を繰り返す回数は O(N)O(N) 回なので、最大カットを容量スケーリング Edmonds-Karp O(M2logiCi)O(M^2 \log \sum_i C_i) で求めることで、この問題を O(NM2logiCi)O(NM^2 \log \sum_i C_i) で解くことができました。

テストケース募集中

2022/05/29 現在、この問題にはランダムケースしかありません。 遅い解法を落とせるハックケースなど、募集中です。 連絡は @0x3b800001 まで。