2021/04/03 - Lru Room

概略

今日は親知らずをぶち抜いてきた. 麻酔をしていたとしても顎外れるんじゃないかと思うレベルで力技で抜かれるので普通にめっちゃ怖かった. そして謎の喪失感があると共に血が滲むのが止まっていない. 今日のご飯はinゼリーにしておこう...

そんなこんなで今日もあまり開発作業は出来ていない. まぁ安静にしてさっさと寝よう.

今日の競プロ

再びのランダム

最短距離が2になる頂点対数がkになるようなグラフを構築する.

連結グラフが条件なので, 各頂点に対して距離が1になるような頂点が少なくとも1つは存在する. 1つの頂点Xに全ての頂点を隣接させると, 頂点X以外の頂点は, 頂点Xへの距離が1となり, それ以外の頂点への距離が全て2になるようなグラフGが構築出来る. こいつが最短距離が2になる頂点対数最大のグラフ.

この時の最短距離が2になる頂点対数は, n-1個の頂点から2個選ぶ組み合わせ数に等しいので,

${}_{n-1} \mathrm{C}_{2} = \frac{(n-1)(n-2)}{2}$

kがこれより大きくなる場合は条件に合うグラフが構築出来ない. kがこれ以下の場合はグラフGの任意の最短距離が2である頂点対の間に辺を追加することで, 最短距離が2である頂点対を1つずつ減らしていくことが出来る. k = 0の場合は完全グラフを書けばよい.

以上からグラフGを作ってから, 最短距離が2になる頂点対数がkになるまで辺をいい感じに足せば終わり

$O(N^2)$

submit result

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, k;
  cin >> n >> k;
  int mx = (n - 1)*(n - 2) / 2;
  int diff = mx - k;

  // 可能な頂点対数を超えていたら-1
  if(diff < 0) {
    cout << -1 << endl;
    return 0;
  }

  // グラフGを作るのに必要な辺数n - 1 + 最短距離2の頂点対数をkに減らすのに必要になる本数
  cout << n - 1 + mx - k << endl;

  // 頂点Nを頂点X扱いとしてグラフGを作る
  for(int i=1; i<n; i++) cout << i << " " << n << endl;

  // 最短距離2の頂点対数をkまで減らす
  int cnt = 0;
  for(int i=1; i<n && cnt<diff; i++){
    for(int j=i+1; j<n && cnt<diff; j++){
      cout << i << " " << j << endl;
      cnt++;
    }
  }
}