最短パス (u,v) を f(u,v) の昇順に数えていけばよいです。一例として以下のような方法が考えられます。
- N 頂点 0 辺のグラフ G と変数 cnt=0 を用意する。
- 各 x∈{Ci} について昇順に以下の操作を行う。
- max(CAj,CBj)=x かつ頂点 Aj と頂点 Bj が連結でないような j が存在しなければ終了する。存在すればそれらのうち一つを選び、(頂点 Aj を含む連結成分のサイズ)×(頂点 Bj を含む連結成分のサイズ) を cnt に加算した後、無向辺 (Aj,Bj) を追加する。
- このとき K≤cnt であれば答えは x である。
- 1.に戻る