Educational Codeforces Round 45 990 D. Graph And Its Complement [구성+도론]
3706 단어 도론
time limit per test:2 seconds
memory limit per test:256 megabytes
input:standard input
output:standard output
Given three numbers n,a,b. You need to find an adjacency matrix of such an undirected graph that the number of components in it is equal to a, and the number of components in its complement is b. 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 n consisting only of "0"and "1", where n is the number of vertices of the graph and the i - th row and the i - th column correspond to the i-th vertex of the graph. The cell (i,j)(i,j) of the adjacency matrix contains 1 if and only if the i - th and j - th vertices in the graph are connected by an edge.
A connected component is a set of vertices X 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 X violates this rule.
The complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G.
Input
In a single line, three numbers are given n,a,b(1≤n≤1000,1≤a,b≤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.
Output
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 n lines, output n digits such that j - th digit of ii-th line must be 1 if and only if there is an edge between vertices i and j in G (and 0 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.
Examples
input
Copy
3 1 2
output
Copy
YES
001
001
110
input
Copy
3 3 3
output
Copy
NO
제목: n개의 점에 무방향도를 만들어야 한다(a개의 연결분량이 있고 보도에는 b개의 연결분량이 있다).
분석: 몇 개를 더 그려 보면 그림과 보정이 적어도 하나는 연결도이다. 그러면 a와 b는 적어도 하나가 1이다. 이렇게 하면 하나의 연결구역이 x인 무방향도를 구성하는 문제로 바뀔 수 있다. 그러나 n==2||n==3을 특판할 때 a, b는 하나만 1이고 n>=4는 두 개가 모두 1인 상황이 나타날 수 있다.
코드:
#include
using namespace std;
const int maxn = 1e3+7;
int n, a, b, v[maxn][maxn];
void solve(int c)
{
puts("YES");
memset(v, 0, sizeof(v));
bool f = true;
if(c < 0) f = false, c = - c;
if(c == 1)
for(int i = 2; i <= n; i++) v[i-1][i] = v[i][i-1] = 1;
else
for(int i = c+1; i <= n; i++) v[i-1][i] = v[i][i-1] = 1;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
printf("%d", f||(i == j) ? v[i][j] : !v[i][j]);
printf("
");
}
}
int main()
{
//freopen("in.txt", "r", stdin);
while(~scanf("%d%d%d", &n, &a,&b)) {
if(a!=1&&b!=1) puts("NO");
else if(a == 1&& b == 1) {
if(n == 1) puts("YES
0");
else if(n < 4) puts("NO");
else solve(1);
} else if(a != 1) solve(a);
else if(b != 1) solve(-b);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 3631 Shortest Path(Floyd + 플러그인)제목: n개의 점 m줄 테두리(단방향 테두리)와 q차 조작을 드리겠습니다. 처음에는 모든 점이 표시가 없습니다. 두 가지 조작이 있습니다. 1.0 x: x를 표시하고 가까이 표시한 경우 "ERROR! At point...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.