[CF 550D] Regular Bridge

作法：

這題我的構造跟官方解的一樣，這裡就寫一下我是怎麼想到的。
因為要有橋，所以大概可以想到把橋的兩邊分開構。因為每個點的度都要是$k$，所以當把橋拔掉後，其中一個連通分量裡每個點的度會長的像：$k-1,k,...,k$。因此當$k$是偶數的時候無解，因為度總和必須是偶數。當$k$奇數時，$k=1$題目構完了，如果$k=3$，先試著構一個度為$2,3,3,3,3$的圖（因為$3$個$3$時奇偶性不對，$3$個以下時點太少），假設五個點分別為$ABCDE$，那麼先連$BD,CE$，剩下的只要再找一個圈就可以了，也就是連上$AB,BC,CD,DE,EA$，這樣就構完$k=3$的情形了。仔細觀察可以發現，其實他就是一個$k+2$接完全圖，拔掉$A$和其中兩個點（$C,D$）連的邊，然後把剩下的點（$B,E$）兩兩配對，把他們之間的邊拔掉所得來的，並且這個構造容易推廣到$k$是更大的奇數的情形，於是在把兩個這樣的圖用橋連起來就做完了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200+10 ;
 
bool G[maxn][maxn] ;
main()
{
    int k ; scanf("%d",&k) ;
    if(k%2==0){printf("NO\n") ; return 0 ;}
    printf("YES\n") ;
    if(k==1){printf("2 1\n1 2\n") ; return 0 ;}
 
    int n=2*(k+2) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        G[i][j]=1 ;
    for(int r=0;r<=k+2;r+=k+2)
    {
        for(int i=2;i<=k;i+=2)
            G[r+i][r+i+1]=G[r+i+1][r+i]=0 ;
        G[r+1][r+k+1]=G[r+k+1][r+1]=0 ;
        G[r+1][r+k+2]=G[r+k+2][r+1]=0 ;
    }
    for(int i=1;i<=k+2;i++) for(int j=k+3;j<=n;j++)
        G[i][j]=G[j][i]=0 ;
    G[1][k+3]=1 ;
 
    int m=0 ;
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
        if(G[i][j]) m++ ;
    printf("%d %d\n",n,m) ;
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
        if(G[i][j]) printf("%d %d\n",i,j) ;
 
}