[AtCoder] ABC 131 E – Friendships

問題

方針

グラフが連結であることから、辺の数は最低でも \( N – 1\) 本必要になります。

構築できるグラフの最短距離が \( 2 \) の頂点対の個数の最大値

辺の数が \( N – 1 \) 本で、頂点 \( 1 \) の次数が \( N – 1 \) のとき、つまり、頂点 \( 1 \) から他の頂点に辺を全て張るとき、最短距離が \( 2 \) の頂点対の個数は、\( \dfrac{(N-1)(N-2)}{2}\) となります。これは、頂点 \( 1 \) 以外の頂点から \( 2 \) つ選ぶ組み合わせの数に対応していることが分かります。

このようなグラフをスターと呼びます。

構築できるグラフの最短距離が \( 2 \) の頂点対の個数の最小値

グラフが完全グラフのとき、全ての頂点対の距離が \( 1 \) となるので、最小値は \( 0 \) となります。

スターから頂点対の距離が \( 2 \) のものを \( 1 \) にする

グラフが頂点 \( 1 \) の次数が \( N – 1 \) のスターであるものを考えます。このとき、頂点 \( i, j\) の距離を \( d(i, j) \) とすると、

\[
\begin{eqnarray}
d(i, i) &=& 0 \\
d(i, 1) &=& 1 \ (i \neq 1)\\
d(1 ,i) &=& 1 \ (i \neq 1)\\
d(i, j) &=& 2 \ (i \neq j \wedge i \neq 1 \wedge j \neq 1)
\end{eqnarray}
\]

となります。また、\( d(i, j) = d(i, 1) + d(1, j) \) となります。

ここで、\(d(i, j) = 2\) となる頂点対に対して、\( d(i, j) = 1 \) となるように辺を張ると、 他の頂点対の距離に影響を与えることなく、頂点対の距離が \( 2 \) のものを \( 1 \) にすることができます。したがって、\( K \leq \dfrac{(N-1)(N-2)}{2}\) のとき、グラフを構築することができます。

コード