#P19003. 图的还原

    ID: 18339 传统题 2000ms 1024MiB 尝试: 33 已通过: 6 难度: 7 上传者: 标签>难度分类提高+/省选-构造与建模图构造枚举与搜索固定一个变量消去另一维暴力枚举全子集枚举状态编码CF2300

图的还原

图的还原

时间限制:2 秒
空间限制:1024 MB
输入输出:标准输入、标准输出

给定一个 n×nn\times n 的整数矩阵 A=(aij)A=(a_{ij})。它满足:

  • 当 i=ji=j、i=1i=1 或 j=1j=1 时,aij=−1a_{ij}=-1。
  • 其余位置的元素均为非负整数。

请构造一张有 nn 个顶点的无向简单图,顶点编号为 1,2,…,n1,2,\ldots,n。无向简单图中没有自环,同一对不同顶点之间至多有一条边。

对于任意两个不同的顶点 i,ji,j,只要 i>1i>1 且 j>1j>1,都必须满足:从这张图中删除顶点 i,ji,j,并删除所有与这两个顶点相连的边后,剩余的边数恰好为 aija_{ij}。

每一对顶点的删除操作相互独立:每次都从原图开始删除。

保证至少存在一张符合要求的图。若有多种答案,输出其中任意一种即可。

输入格式

第一行包含一个整数 TT,表示测试用例数。

每个测试用例的第一行包含一个整数 nn。

接下来 nn 行,每行包含 nn 个整数,依次为矩阵的一行。

输出格式

对于每个测试用例,输出所构造图的邻接矩阵,共 nn 行,每行 nn 个整数。所有整数只能是 00 或 11。

第 ii 行第 jj 个数为 11,当且仅当图中存在连接顶点 i,ji,j 的边。

样例输入

2
5
-1 -1 -1 -1 -1
-1 -1 3 1 2
-1 3 -1 2 2
-1 1 2 -1 1
-1 2 2 1 -1
7
-1 -1 -1 -1 -1 -1 -1
-1 -1 4 5 3 6 5
-1 4 -1 5 4 5 5
-1 5 5 -1 5 7 5
-1 3 4 5 -1 4 4
-1 6 5 7 4 -1 5
-1 5 5 5 4 5 -1

样例输出

0 1 0 1 1
1 0 0 0 0
0 0 0 1 0
1 0 1 0 1
1 0 0 1 0
0 1 1 0 1 0 0
1 0 0 0 0 1 1
1 0 0 0 1 0 1
0 0 0 0 1 1 0
1 0 1 1 0 0 1
0 1 0 1 0 0 0
0 1 1 0 1 0 0

样例输出只是一组可行答案。

数据范围

对于所有测试用例:

  • 1≤T≤6×1041\le T\le 6\times10^4。
  • 4≤n≤10004\le n\le 1000。
  • −1≤aij≤(n−3)(n−2)2-1\le a_{ij}\le \dfrac{(n-3)(n-2)}2,并满足题目所述的矩阵条件。
  • 所有测试用例的 n2n^2 之和不超过 1.2×1061.2\times10^6。
  • 保证存在符合要求的图。

本次校内测试采用以下 100 分子任务。这是本校设置的评分方式;每个子任务内全部测试通过才获得该子任务的分数,各子任务独立计分。

子任务 分值 附加限制
1 10 n≤5n\le5
2 15 n≤30n\le30
3 保证至少存在一张顶点 11 的度数为 00 的合法图
4 20 n≤300n\le300
5 40 无附加限制

所有子任务均满足完整数据范围。


题目原作:电子科技大学命题组,2026 ICPC 成都区域赛。中文整理及本校评分分组已作调整;题面遵循 CC BY-SA 4.0。

下发文件

大样例输入与一种合法输出

本题答案可能不唯一,样例输出仅为一种合法方案。