AtCoder ABC #131 : E - Friendships

誤読さえなければなぁ…。
https://atcoder.jp/contests/abc131/tasks/abc131_e

問題

N頂点の単純無向グラフのうち、最短経路長が2の頂点対がK個あるものを構築せよ。

解法

狙って経路長が2の物を増やそうとするとめんどう。
ただ減らすのは容易である。すでに最短経路がu-v-wであるとき、u-w間に辺を追加すれば経路長2の組は1つ減る。
これだと経路長3の組が2になりかねないので、最初から経路長3以上のものを作らないでおこう。

そこで、まず頂点1とそれ以外を全部つなぐ。
この状態で経路長が2の対はComb(N-1,2)通りある。
あとは条件を満たす対の数がK個なるまで、上記の手順で辺を追加しよう。

int N,K;
vector<pair<int,int>> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	int lef=(N-1)*(N-2)/2;
	if(K>lef) return _P("-1\n");
	
	for(i=2;i<=N;i++) V.push_back({1,i});
	lef-=K;
	for(x=2;x<=N;x++) for(y=x+1;y<=N;y++) if(lef) {
		lef--;
		V.push_back({x,y});
	}
	
	cout<<V.size()<<endl;
	FORR(v,V) cout<<v.first<<" "<<v.second<<endl;
	
	
	
	
}

まとめ

最初木を作る問題と勘違いして大量に時間を溶かした。