同构图+思维构造——牛客多校第六场E

ゝ一世哀愁。 2023-10-11 09:13 5阅读 0赞

考的其实是同构图的性质：

1.同构图的顶点数，边数相等

2.同构图通过点的映射后邻接矩阵相同

这篇博客讲的很好[https://www.jianshu.com/p/c33b5d1b4cd9][https_www.jianshu.com_p_c33b5d1b4cd9]

本题还需要一步构造的方案，通过最基础的n=4和n=4+1的图的图推广到n=4k和n=4k+1的状态

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 2005
    int mp[maxn][maxn];
    int n,f[maxn];
    int main(){
        int t;cin>>t;
        for(int tt=1;tt<=t;tt++){
            cin>>n;
            if(n%4==2 || n%4==3){
                printf("Case #%d: No\n",tt);
                continue;
            }
            memset(mp,0,sizeof mp);
            memset(f,0,sizeof f);
            int m=n/4;//分成四个块 
            for(int i=1;i<=m;i++)//两个团 
                for(int j=1;j<=m;j++)    
                    if(i!=j){
                        mp[i][j]=1,mp[i+3*m][j+3*m]=1;
                    }
            for(int i=1;i<=m;i++)//块之间的边 
                for(int j=1;j<=m;j++){
                    mp[i][j+m]=mp[j+m][i]=1;
                    mp[i+m][j+2*m]=mp[j+2*m][i+m]=1;
                    mp[i+2*m][j+3*m]=mp[j+3*m][i+2*m]=1;
                }
            if(n%4==1){
        //额外点 
                for(int i=1;i<=m;i++){
                    mp[n][i]=mp[i][n]=1;
                    mp[n][i+3*m]=mp[i+3*m][n]=1;
                }
            }
            //构造映射关系 
            for(int i=1;i<=m;i++){
                f[i]=i+m;f[i+m]=i+3*m;f[i+2*m]=i;f[i+3*m]=i+2*m;
            }
            if(n%4==1)f[n]=n;
            printf("Case #%d: Yes\n",tt);
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++)
                    cout<<mp[i][j];
                puts("");
            }
            for(int i=1;i<n;i++)cout<<f[i]<<" ";
            cout<<f[n]<<'\n';
        } 
    }

转载于:https://www.cnblogs.com/zsben991126/p/11296815.html

[https_www.jianshu.com_p_c33b5d1b4cd9]: https://www.jianshu.com/p/c33b5d1b4cd9