시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 128 MB | 5 | 1 | 1 | 100.000% |
바이트랜드에서 벌어졌던 오랜 전쟁이 끝났다. 정부에서는 가장 먼저 교통 수단부터 복구하기로 결정하였다.
바이트랜드는 두 개의 섬으로 이루어져 있다.
전쟁 이전, 각 섬 내의 모든 도시들은 하나의 양방향 선로로 서로 직접 연결되어 있었으며, 전쟁 도중 몇 개의 선로가 파괴되었다. 전쟁 도중 파괴된 선로는 15개를 넘지 않는다.
전쟁 이전까지만 해도 두 섬간의 교류는 불가능했으나, 이번 복구작업을 마친 후 두 섬 사이를 왕복하는 페리선을 놓아 바이트랜드의 모든 도시들이 하나의 항로 혹은 선로로 연결되게 하려고 한다.
즉, 같은 섬에 있지 않은 모든 서로 다른 두 도시 쌍의 사이에는 페리선 항로가 존재해야 하며, 같은 섬에 있는 모든 서로 다른 두 도시 쌍의 사이에는 열차 선로가 존재해야 한다.
바이트랜드에서는 모든 것이 이진수로 표기된다. 당연히 모든 기차 티켓과 페리선 티켓의 가격 또한 0 또는 1원이다.
우선 정부에서는 파괴되지 않은 선로들에 매겨져 있던 티켓 가격은 그대로 쓰기로 결정하였다.
또한 이번에 새로 복구할 선로와 새로 만들 페리선 항로에 대하여 항상 다음과 같은 규칙이 성립하도록 하려고 한다.
어떤 서로 다른 세 도시 X, Y, Z가 있을 때, 두 도시를 직접 잇는 선로 혹은 항로의 티켓 가격이 C라 하면
C(X, Y) + C(Y, Z) ≥ C(X, Z)
즉, 직행 경로의 비용은 항상 다른 도시를 경유한 경로보다 저렴하거나 같은 비용을 가져야 한다.
바이트랜드의 두 섬의 도로 정보가 주어졌을 때, 규칙에 맞게 도로와 항로를 복구하고 개설할 수 있는지 판정하고, 만일 가능하다면 바이트랜드의 최종 교통 계획은 어떻게 될지 직접 구해보자.
첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 100 )
각 테스트 케이스는 다음과 같이 구성된다.
주어지는 표는 항상 대각선 대칭이며, i번째 행 i번째 열의 값은 항상 0이다.
각각의 주어지는 표에서 x의 개수는 합해서 30개를 넘지 않는다. (표는 항상 대칭이므로 파괴된 도로 하나당 x가 두 개씩 표에 출현한다.)
입력에서 파괴되지 않은 도로들이 이미 규칙을 지키지 않고 있을 수 있음에 주의하라.
각 테스트 케이스마다, 규칙에 맞게 교통 계획을 세울 수 있다면 YES를, 불가능하다면 NO를 출력한다.
YES를 출력할 경우, 이어 C 1 + C2줄에 걸쳐 C1 + C2개의 문자로 최종 교통 계획을 출력한다. 이때, 섬 1의 도시는 1부터 C1까지의 번호를 가지며, 섬 2의 도시는 C1 + 1번부터 C2번까지의 번호를 갖는다. 이 조건 하에서, i번째 행의 j번째 열의 숫자는 i번 도시와 j번 도시를 잇는 선로/항로의 티켓 가격이 되어야 한다. (0 또는 1)
결과는 대칭 행렬이어야 하며, 조건을 만족하는 선로/항로 배치가 여러 가지인 경우 그 중 아무 것이나 출력한다.
2 3 011 10x 1x0 2 01 10 2 0x x0 4 010x 1010 0100 x000
YES 01101 10011 10011 01101 11110 NO
ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2012 Arab Collegiate Programming Contest H번