CF550D Regular Bridge

图论——桥+构造

首先证明当k为偶数时不可行

题目说至少有一个桥，那么就先考虑只有一个桥的情况

设这个联通分量中有 x 个点

在一个联通分量里有一条边连向另一个联通分量中，度用去 1

此时点剩余的度有 k*x-1 

因为k为偶数，所以 k*x-1 为奇数

又因为一条边贡献 2 度

所以不可行

同理若有多个桥，则没有其他来自另外联通分量的边的联通分量 同上

那么 k 一定为奇数

只考虑只有一个桥的情况

让一个联通分量有 2*k+2 个点

k个点为完全图，删掉 (k-1)/2 条边，使除了最上面的点（这个点与其他的 k-1 个点都有一条边）的度为 k-2 

然后将这 k-1 个点连到桥连着的那个点上去

此时这 k 个点都有 k-1 度，再重新设一个点，与这 k 个点都连一条边，即可

#include <bits/stdc++.h>
using namespace std;
int k,n,m,w;
int main()
{
    scanf("%d",&k);
    if (k%2==0)
    {
        printf("NO
");
        return 0;                                                                                                                                                                                                                                            
    }
    if (k==1)
    {
        printf("YES
2 1
1 2
");
        return 0;
    }
    n=2*k+4;
    m=k*k+2*k;
    printf("YES
");
    printf("%d %d
",n,m);
    for (int i=1;i<=k-1;i++)
    {
        for (int j=i+1;j<=k-1;j++)
        {
            if (i%2==1 && i+1==j)
              continue;
            printf("%d %d
",i,j);
        }
        printf("%d %d
",k,i);
        printf("%d %d
",2*k+3,i);
        printf("%d %d
",2*k+1,i);
    }
    printf("%d %d
",2*k+3,k);
    for (int i=k+1;i<=2*k-1;i++)
    {
        for (int j=i+1;j<=2*k-1;j++)
        {
            if (i%2==0 && i+1==j)
              continue;
            printf("%d %d
",i,j);
        }
        printf("%d %d
",2*k,i);
        printf("%d %d
",2*k+4,i);
        printf("%d %d
",2*k+2,i);
    }
    printf("%d %d
",2*k+4,2*k);
    printf("%d %d
",2*k+1,2*k+2);
}