解説

最小カットの性質

$G$ における最短距離を $d(u,v)$、頂点 $v$ からの距離和を $D_v=\sum_{u=1}^{N}d(v,u)$ とします。 $H$ の頂点 $1,N$ 間の最小カットの容量は、$\min(D_1,D_N)$ です。

これを示します。 頂点 $1$ または $N$ だけを切り離せば、容量がそれぞれ $D_1,D_N$ のカットを作れます。 したがって、任意のカットの容量が $\min(D_1,D_N)$ 以上であることを示せば十分です。

カットを $S=\{1\}\cup X,T=\{N\}\cup Y$ とし、その容量を $C$ とします。 片側が単独の頂点である場合は明らかなので、$p=|X|\ge1,q=|Y|\ge1$ とします。 $X,Y$ 間の容量の和を $R=\sum_{x\in X,y\in Y}d(x,y)$ と置きます。

三角不等式より、各 $x\in X,y\in Y$ について

$$d(1,x)+d(N,y)\le d(1,y)+d(N,x)+2d(x,y)$$

です。 これをすべての組について足し、$C=d(1,N)+\sum_{y\in Y}d(1,y)+\sum_{x\in X}d(N,x)+R$ を使って整理すると、

$$qD_1+pD_N\le(p+q)C-(p+q-2)R\le(p+q)C$$

となります。 よって $C\ge\min(D_1,D_N)$ が成り立ちます。

以降は、$\min(D_1,D_N)=K$ となるグラフを構築します。

必要条件

実現可能な $K$ は、次の範囲に限られます。 ただし、$\binom N2=N(N-1)/2$ とします。

$$N-1\le K\le\binom N2-\left\lfloor\frac{N-1}{2}\right\rfloor \quad\text{または}\quad K=\binom N2$$

下限は、異なる頂点間の距離が $1$ 以上であることから従います。 上限を示すため、頂点 $1,N$ 間の最短路を一つ取り、その長さを $L$、最短路の外にある頂点数を $r=N-L-1$ とします。

最短路上の頂点 $v$ については $d(1,v)+d(N,v)=L$ です。 最短路の外にある頂点 $v$ から最短路までの距離を $h_v$ とすると、最短路を経由することで

$$d(1,v)+d(N,v)\le L+2h_v$$

が成り立ちます。 また、$r$ 個の $h_v$ を昇順に並べると、$i$ 番目の値は $i$ 以下です。 距離が $h$ の頂点が存在するには、距離が $1,2,\ldots,h-1$ の頂点も必要だからです。 したがって、$\sum h_v\le r(r+1)/2$ より

$$D_1+D_N\le NL+r(r+1)=N(N-1)-Lr$$

となります。

$r\ge1$ の場合、$L,r\ge1$ と $L+r=N-1$ より $Lr\ge N-2$ なので、

$$\min(D_1,D_N) \le\left\lfloor\frac{D_1+D_N}{2}\right\rfloor \le\binom N2-\left\lfloor\frac{N-1}{2}\right\rfloor$$

です。 $r=0$ の場合、最短路が全頂点を通ります。 パス上で隣接しない頂点を結ぶ辺があると最短路が短くなるため、$G$ はパスそのものであり、$K=\binom N2$ となります。

構築方法

頂点 $1,N$ を両端とする長さ $L$ のパスを作り、残りの $r=N-L-1$ 頂点を葉としてパスに付けます。 葉 $i$ を頂点 $1$ から $x_i$ 辺進んだ位置に付けると、その葉と頂点 $1,N$ の距離は、それぞれ $x_i+1,L-x_i+1$ です。

$$B_L=\frac{L(L+1)}2+r=N-1+\frac{L(L-1)}2,\qquad Q=\sum_{i=1}^{r}x_i$$

と置くと、両端からの距離和は

$$D_1=B_L+Q,\qquad D_N=B_L+rL-Q$$

となります。 各 $x_i$ は $0$ 以上 $L$ 以下の任意の整数にできるため、$Q$ は $0$ から $rL$ までのすべての整数を取れます。 よって、固定した $L$ で実現できる値は、次の区間です。

$$B_L\le K\le U_L, \qquad U_L=B_L+\left\lfloor\frac{rL}{2}\right\rfloor =N-1+\left\lfloor\frac{L(N-2)}2\right\rfloor$$

この構築で、必要条件を満たすすべての $K$ を実現できます。 $N\ge3$ のとき、$L=1,\ldots,N-2$ に対応する区間の最初の下端と最後の上端は

$$B_1=N-1,\qquad U_{N-2}=\binom N2-\left\lfloor\frac{N-1}{2}\right\rfloor$$

です。 また、$1\le L\le N-3$ では $r\ge2$ なので、

$$B_{L+1}-U_L=L-\left\lfloor\frac{Lr}{2}\right\rfloor\le0$$

となり、隣り合う区間は重なります。 残る $K=\binom N2$ は、$L=N-1$ としてパスだけを作れば実現できます。 $N=2$ の場合も、このパスで唯一可能な値 $K=1$ を実現できます。

実装では、$L=1,2,\ldots,N-1$ を調べ、$B_L\le K\le U_L$ を満たすものを一つ選びます。 見つからなければ -1 を出力します。

$L$ が見つかったら、$Q=K-B_L$ とし、各葉について $x_i=\min(L,Q)$、$Q\gets Q-x_i$ と貪欲に割り当てます。 最初の $Q$ は $\lfloor rL/2\rfloor$ 以下なので、$r$ 個の葉で必ず割り当てが完了し、構築後は $D_1=K\le D_N$ となります。 パスの両端に $1,N$、ほかの頂点に残りの番号を割り当てれば完成です。

構築するグラフは $N$ 頂点 $N-1$ 辺の木であり、単純かつ連結です。 パスの長さの探索と構築を合わせて、各テストケースの時間計算量は $O(N)$ です。