2265 - Spanning Trees

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2264

問題

略

解法

公式の講評の解法１の通り。
偶数の場合はn=2を元として4からスタート、奇数の場合はn=3を元として5からスタートして全域木を更新、追加していく。追加はkまで。
coutだと間に合わなそう。

何故set使ったんだろう。

ソース

typedef pair<int,int> pii;
int main() {
  int n,k;
  cin >> n >> k;
  if (2*k>n) {
    cout << -1 << endl;
    return 0;
  }
  set<pii> se[k+1];
  se[0].insert(pii(1,2));
  int start = 4;
  if (n%2) {
    se[0].insert(pii(2,3));
    start = 5;
  }
  for (int i=start; i<=n; i+=2) {
    for (int j=1; j<=min(i/2-1, k); ++j) { // 頂点の数を増やす
      se[j-1].insert(pii(i-1, j));
      se[j-1].insert(pii(i, i/2-1+j));
    }
    if (i/2<=k) { // 新たにひとつ作る
      int hoge = i/2-1;
      se[hoge].insert(pii(i-1, i));
      for (int j=1; j<=i/2-1; ++j) {
        se[hoge].insert(pii(i, j));
        se[hoge].insert(pii(i-1, i/2-1+j));
      }
      if (n%2) se[hoge].insert(pii(i-1,i-2));
    }
  }
  REP(i,k) {
    if (i)puts("");
    FOR(it, se[i]) {
      printf("%d %d\n",it->first, it->second);
    }
  }
}