CF990D.Graph And Its Complement

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Given three numbers n,a,bn, a, b . You need to find an adjacency matrix of such an undirected graph that the number of components in it is equal to aa , and the number of components in its complement is bb . The matrix must be symmetric, and all digits on the main diagonal must be zeroes.

In an undirected graph loops (edges from a vertex to itself) are not allowed. It can be at most one edge between a pair of vertices.

The adjacency matrix of an undirected graph is a square matrix of size nn consisting only of "0" and "1", where nn is the number of vertices of the graph and the ii -th row and the ii -th column correspond to the ii -th vertex of the graph. The cell (i,j)(i,j) of the adjacency matrix contains 11 if and only if the ii -th and jj -th vertices in the graph are connected by an edge.

A connected component is a set of vertices XX such that for every two vertices from this set there exists at least one path in the graph connecting this pair of vertices, but adding any other vertex to XX violates this rule.

The complement or inverse of a graph GG is a graph HH on the same vertices such that two distinct vertices of HH are adjacent if and only if they are not adjacent in GG .

输入格式

In a single line, three numbers are given n,a,b(1n1000,1a,bn)n, a, b \,(1 \le n \le 1000, 1 \le a, b \le n) : is the number of vertexes of the graph, the required number of connectivity components in it, and the required amount of the connectivity component in it's complement.

输出格式

If there is no graph that satisfies these constraints on a single line, print "NO" (without quotes).

Otherwise, on the first line, print "YES"(without quotes). In each of the next nn lines, output nn digits such that jj -th digit of ii -th line must be 11 if and only if there is an edge between vertices ii and jj in GG (and 00 otherwise). Note that the matrix must be symmetric, and all digits on the main diagonal must be zeroes.

If there are several matrices that satisfy the conditions — output any of them.

输入输出样例

  • 输入#1

    3 1 2
    

    输出#1

    YES
    001
    001
    110
    
  • 输入#2

    3 3 3
    

    输出#2

    NO
    
首页