Codeforce 550 D. Regular Bridge 解析(思維、圖論)

今天我們來看看CF550D
題目連結

題目
給你一個$k\le100$，請構造出一個至少有一個Bridge的，每個點的degree都是$k$的無向圖。

前言

學到了Handshaking Lemma

想法

首先既然要有一個Bridge，我們就從已經有一個Bridge的圖開始構造。
可能會發現到$k=2$無解，而$k=3$($k$是奇數)有以下這個解(我一開始根本沒想到):
首先只考慮Bridge的一邊，然後必然有$k-1=2$條邊連出去，接著我們再多連出去一個點(2—4,3—5)，然後$leaf(點4,5)$連到右方所有還沒滿的點，接著$leaf$再兩兩連起來。

接著證明當$k\mod 2=0$時無解:首先只考慮Bridge的一邊，接著我們會發現連接Bridge的那個點的度數是$k-1$，是奇數，而其他點的度數都是$k$，是偶數。根據Handshaking Lemma，無解。(如果不知道這個Lemma也可以直接證明不存在，只是比較繁瑣)

程式碼:

const int _n=1e6+10;  
int t,n,k;   
vector<PII> e;  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>k;if(k%2==0){cout<<"NO\n";return 0;}  
  rep(i,2,k+1)e.pb({1,i});rep(i,k+1,2*k)rep(j,2,k+1)e.pb({i,j});  
  for(int i=k+1;i<=2*k-2;i+=2)e.pb({i,i+1});  
  cout<<"YES\n"<<4*k-2<<' '<<2*SZ(e)+1<<'\n';  
  rep(i,0,SZ(e))cout<<e[i].fi<<' '<<e[i].se<<'\n';  
  rep(i,0,SZ(e))cout<<e[i].fi+2*k-1<<' '<<e[i].se+2*k-1<<'\n';  
  cout<<1<<' '<<2*k<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission