AtCoder Grand Contest 032 B - Balanced Neighbors—

题意

B - Balanced Neighbors

给定一个整数 $N$（$3\leq N \leq 100$），构造一个顶点编号为 $1...N$ 的无向图，需满足如下两个条件：

简单图且连通
存在一个整数 $S$，使得对于每个顶点，与其相连的顶点的编号和都为 $S$

可以证明至少有一个满足上述条件的图，请输出这样的图。

分析

手动尝试一下 $n=3,4,5$，可以找到一个构造方法。

考虑完全 $k$ 分图（类比完全二分图）,并保证这 $k$ 部分的和都相等。

如果 $n$ 为偶数，那么我们可以两联配对，即 $\{1,n \}, \{2,n-1 \},..., \{ n/2, n/2+1\}$.

如果 $n$ 为奇数，那么我们把 $n$ 单独拿出来作为一组，剩余的 $n-1$ 个两两配对。

这样构造的图在 $n \geq 3$ 时连通性易证。

#include<bits/stdc++.h>

using namespace std;

int n;

int a[][];

void solve()

{

    if(n&) n = n-;         //奇数化成偶数

    for(int i = ;i <= n/;i++)

    {

        a[i][] = i;

        a[i][] = n+-i;

    }

    for(int i = ;i <= n/;i++)

        for(int j = ;j < ;j++)

            for(int k = i+;k <= n/;k++)

                for(int t = ;t < ;t++)

                    printf("%d %d\n", a[i][j], a[k][t]);

}

int main()

{

    scanf("%d", &n);

    int m =  * (n/) * (n/ - );

    if(n & )

    {

        printf("%d\n", m + n - );

        for(int i = ;i < n;i++)  printf("%d %d\n", n, i);

        solve();

    }

    else

    {

        printf("%d\n", m);

        solve();

    }

    return ;

}

参考链接：https://oi-wiki.org/basic/construction/

巴特西

AtCoder Grand Contest 032 B - Balanced Neighbors——构造

题意

分析

最新文章

热门文章