---
title: Codeforce 550 D. Regular Bridge 解析(思維、圖論)
description: "Codeforce 550 D. Regular Bridge 解析(思維、圖論)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 550 D. Regular Bridge 解析(思維、圖論)">
<!-- toc -->

# Codeforce 550 D. Regular Bridge 解析(思維、圖論)
今天我們來看看CF550D
[題目連結](https://codeforces.com/problemset/problem/550/D)

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

### 前言
學到了Handshaking Lemma

<div class="VVVcopyrightAAA";>@copyright petjelinux 版權所有<br>
<a href="https://www.cnblogs.com/petjelinux/">觀看更多正版原始文章請至petjelinux的blog</a></div>

### 想法
首先既然要有一個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](https://codeforces.com/contest/550/submission/91709776)