Codeforces Round #423B: High Load

http://codeforces.com/contest/827/problem/B

最初にrootを一つ決めて、あとはkコずつrootからまんべんなくつけていけば、木の高さが最小、かつその時の一番rootから離れているedgeの個数も最小になるのでこれが求めるグラフとなる。

int N, K;

void solve() {
	cin >> N >> K;
	if((N - K - 1) % K == 0) cout << (N - K - 1) / K * 2 + 2 << "\n";
	else if((N - K - 1) % K == 1) cout << (N - K - 1) / K * 2 + 3 << "\n";
	else cout << (N - K - 1) / K * 2 + 4 << "\n";
	vector<int> vec;
	rep(i, 0, K) vec.push_back(i + 1);
	int at = K + 1;
	while(at < N) {
		int a = vec[(at - 1) % K];
		cout << a << " " << at << "\n";
		vec[(at - 1) % K] = at;
		at++;
	}
	rep(i, 0, K) {
		cout << vec[i] << " " << N << "\n";
	}
}

こういうのをウニグラフというらしい。