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

时间:2023-03-10 06:47:44
D. Regular Bridge 解析(思維、圖論)

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

今天我們來看看CF550D

題目連結

題目

給你一個\(k\le100\),請構造出一個至少有一個Bridge的,每個點的degree都是\(k\)的無向圖。

前言

學到了Handshaking Lemma

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

想法

首先既然要有一個Bridge,我們就從已經有一個Bridge的圖開始構造。

可能會發現到\(k=2\)無解,而\(k=3\)(\(k\)是奇數)有以下這個解(我一開始根本沒想到):

首先只考慮Bridge的一邊,然後必然有\(k-1=2\)條邊連出去,接著我們再多連出去一個點(2---4,3---5),然後\(leaf(點4,5)\)連到右方所有還沒滿的點,接著\(leaf\)再兩兩連起來。

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

接著證明當\(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