ABC131 E - Friendships (500)

概要

2以上の整数Nと整数Kが与えられる。このときN頂点M辺の無向グラフで下記のものが存在するかどうかを判定せよ。もし存在するならそのグラフを出力し、存在しないなら-1を出力せよ。

• グラフは単純かつ連結
• グラフには最短距離が2であるような頂点対(i, j) (i < j) がちょうどK個存在する

制約

2 ≦ N ≦ 100
0 ≦ K ≦ N * (N - 1) / 2

方針

下記のように、1つの頂点から他の全ての頂点に辺が張られているグラフを考える。

実はこのグラフが最短距離2の頂点対の数が最大になる場合であり、そのような頂点対は(N - 2) * (N - 3) / 2 個存在する。上記のN = 5 の場合は(2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5) の6個存在する。

Kと(N - 2) * (N - 3) / 2 の大小関係によって処理を場合分けしてゆく。
Kが(N - 2) * (N - 3) / 2 より大きい場合は-1を出力する。
Kが(N - 2) * (N - 3) / 2 の場合は上記のようなグラフをそのまま出力する。

Kが(N - 2) * (N - 3) / 2 より小さい場合は、最短距離が2となる頂点対に辺を張ることで、その分頂点対の数を減らすことが出来る。

下記は最初のグラフから(2, 3), (3, 4) に辺を張ったグラフである。
このグラフは最短距離が2となる頂点対が(2, 4), (2, 5), (3, 5), (4, 5) の4個となっている。

解答

Submission #6088587 - AtCoder Beginner Contest 131

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, K;
	cin >> N >> K;
 
	int x = (N-1) * (N-2) / 2;
	if(K > x){
		cout << -1 << endl;
		return 0;
	}
 
	int max_cnt = x - K;
	cout << N - 1 + max_cnt << endl;
	for(int i = 0; i < N - 1; i++){
		cout << 1 << " " << (i+2) << endl;
	}
 
	int a = 2;
	int b = 3;
	for(int i = 0; i < max_cnt; i++){
		cout << a << " " << b << endl;
		if(b == N){
			b = a + 2;
			a++;
		}else{
			b++;
		}
	}
 
}