D. Graph And Its Complement[構造題]

D. Graph And Its Complement

題意:給定a,b.要求構造一個鄰接矩陣,對應的圖中,有a個聯通塊  ； 對應的補圖有b個聯通塊

思路:

假設a>1,那麼b一定為1.說明a,b中至少有一個是1.特判構造

a>1,前a-1個獨立,為a-1個聯通塊；[a+1,n]頂點為一個聯通塊

a==1,b>1.構造補圖的,再傳回來

a==1,b==1.n=1成立,n=2,n=3不成立.n>=4,就是一個鍊

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
#define debug puts
#define setp cout << fixed << setprecision(3)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int N=1e3+3;
const int MOD=1e9+7;
const ll INF=1e18+8;
int ans[N][N];
int main(void){
    FAST_IO;
    int n,a,b;
    cin >>n >> a>>b;
    if(a!=1&&b!=1){
        cout <<"NO"<<endl;
        return 0;
    }
    if(a!=1){
        for(int i=a+1;i<=n;i++){
            ans[a][i]=ans[i][a]=1;
        }
    }
    else if(b!=1){
        for(int i=b+1;i<=n;i++){
            ans[b][i]=ans[i][b]=1;
        }
        cout <<"YES"<<endl;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j)    cout << 0;
                else if(ans[i][j])  cout << 0;
                else    cout << 1;
            }
            cout <<"\n";
        }
        return 0;
    }
    else if(a==1&&b==1){
        if(n==1){

        }
        else if(n==2||n==3){
            cout <<"NO"<<endl;
            return 0;
        }
        else{
            int now=1;
            for(int i=2;i<=n;i++){
                ans[i][now]=ans[now][i]=1;
                now=i;
            }
        }
    }
    cout <<"YES"<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)   cout <<ans[i][j];
        cout<<"\n";
    }

    return 0;
}