[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}\) のとき、グラフを構築することができます。
コード
#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; }
ディスカッション
コメント一覧
まだ、コメントがありません