牛客多校第六场 E Androgynos 自补图

题意：

给定点数，构造自补图，要求输出邻接矩阵，和原图与补图的同构映射。

题解：

只有点数为4k和4k+1的情况才能构造自补图，因为只有这些情况下边数才为偶数。

一种构造方式是，邻接矩阵和同构映射增量构造，每次加四个边xyzw，x和w连接原来的所有边，yz不连，同构映射是交换xy，zw

参考：www.matrix67.com/blog/archives/6221

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int M = 2e3 + ;

const LL mod = ;

const LL lINF = 0x3f3f3f3f3f3f3f3f;

bool mp[M][M];

int t;

int n;

int a[M];

int main()

{

    scanf("%d", &t);

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

    {

        scanf("%d", &n);

        if (n %  == )

        {

            printf("Case #%d: Yes\n", cnt);

            memset(mp, , sizeof mp);

            mp[][] = mp[][] = ;

            mp[][] = mp[][] = ;

            mp[][] = mp[][] = ;

            a[] = ;

            a[] = ;

            a[] = ;

            a[] = ;

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

            {

                mp[i][i + ] = mp[i + ][i] = ;

                mp[i + ][i + ] = mp[i + ][i + ] = ;

                mp[i + ][i + ] = mp[i + ][i + ] = ;

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

                {

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

                    {

                        mp[i + j][k] = mp[k][i + j] = ;

                    }

                }

                a[i] = i + ;

                a[i + ] = i;

                a[i + ] = i + ;

                a[i + ] = i + ;

                swap(a[i+], a[i + ]);

            }

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

            {

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

                {

                    printf("%d", mp[i][j]);

                }

                puts("");

            }

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

            {

                printf("%d ", a[i]);

            }

            printf("%d\n", a[n]);

        }

        else if (n %  == )

        {

            printf("Case #%d: Yes\n", cnt);

            memset(mp, , sizeof mp);

            a[] = ;

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

            {

                mp[i][i + ] = mp[i + ][i] = ;

                mp[i + ][i + ] = mp[i + ][i + ] = ;

                mp[i + ][i + ] = mp[i + ][i + ] = ;

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

                {

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

                    {

                        mp[i + j][k] = mp[k][i + j] = ;

                    }

                }

                a[i] = i + ;

                a[i + ] = i;

                a[i + ] = i + ;

                a[i + ] = i + ;

                swap(a[i+], a[i + ]);

            }

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

            {

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

                {

                    printf("%d", mp[i][j]);

                }

                puts("");

            }

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

            {

                printf("%d ", a[i]);

            }

            printf("%d\n", a[n]);

        }

        else

        {

            printf("Case #%d: No\n", cnt);

        }

    }

}

巴特西

牛客多校第六场 E Androgynos 自补图

最新文章

热门文章