#P19003. 图的还原
图的还原
图的还原
时间限制:2 秒
空间限制:1024 MB
输入输出:标准输入、标准输出
给定一个 的整数矩阵 。它满足:
- 当 、 或 时,。
- 其余位置的元素均为非负整数。
请构造一张有 个顶点的无向简单图,顶点编号为 。无向简单图中没有自环,同一对不同顶点之间至多有一条边。
对于任意两个不同的顶点 ,只要 且 ,都必须满足:从这张图中删除顶点 ,并删除所有与这两个顶点相连的边后,剩余的边数恰好为 。
每一对顶点的删除操作相互独立:每次都从原图开始删除。
保证至少存在一张符合要求的图。若有多种答案,输出其中任意一种即可。
输入格式
第一行包含一个整数 ,表示测试用例数。
每个测试用例的第一行包含一个整数 。
接下来 行,每行包含 个整数,依次为矩阵的一行。
输出格式
对于每个测试用例,输出所构造图的邻接矩阵,共 行,每行 个整数。所有整数只能是 或 。
第 行第 个数为 ,当且仅当图中存在连接顶点 的边。
样例输入
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
样例输出只是一组可行答案。
数据范围
对于所有测试用例:
- 。
- 。
- ,并满足题目所述的矩阵条件。
- 所有测试用例的 之和不超过 。
- 保证存在符合要求的图。
本次校内测试采用以下 100 分子任务。这是本校设置的评分方式;每个子任务内全部测试通过才获得该子任务的分数,各子任务独立计分。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 10 | |
| 2 | 15 | |
| 3 | 保证至少存在一张顶点 的度数为 的合法图 | |
| 4 | 20 | |
| 5 | 40 | 无附加限制 |
所有子任务均满足完整数据范围。
题目原作:电子科技大学命题组,2026 ICPC 成都区域赛。中文整理及本校评分分组已作调整;题面遵循 CC BY-SA 4.0。
下发文件
本题答案可能不唯一,样例输出仅为一种合法方案。
相关
在下列比赛中: