[AtCoder] ABC 131 E – Friendships

2019年6月23日

問題

方針

グラフが連結であることから、辺の数は最低でも \( 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}\) のとき、グラフを構築することができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, K;
  cin >> N >> K;
  vector<pair<int, int>> G;
  for (int i = 2; i <= N; i++) {
    G.push_back(make_pair(1, i));
  }
  int d = (N - 1) * (N - 2) / 2;
  int res = d - K;
  if (res < 0) {
    cout << "-1\n";
    return 0;
  }
  for (int i = 2; i < N; i++) {
    for (int j = i + 1; j <= N; j++) {
      if (res == 0) goto loop;
      res--;
      G.push_back(make_pair(i, j));
    }
  }
  loop:
  cout << G.size() << "\n";
  for (int i = 0; i < G.size(); i++) {
    cout << G[i].first << " " << G[i].second << "\n";
  }
  return 0;
}