#P18812. [Croatian CPC 2026]Bridovi Brljaju
[Croatian CPC 2026]Bridovi Brljaju
Bridovi Brljaju
题目描述
给定两个顶点集合均为 的无向简单图,分别称为初始图和目标图。两图都没有自环和重边。你需要通过以下操作将初始图变成目标图。
一次操作选择一个顶点 ,以及编号变化方向:增加或减少。对于操作前存在的每条边 ,将其替换为 ,其中 是将 沿指定方向循环移动一个编号、并跳过 后得到的编号。
编号增加时, 的下一个编号是 ;编号减少时, 的上一个编号是 。如果移动一步到达 ,则沿相同方向再移动一步。
所有边的替换都依据操作前的图同时进行。因为图是无向的,其他顶点与 的连接关系也随之改变。不与 相连的边保持不变。
更形式化地,定义循环后继 和循环前驱 :
$$p(u)=\begin{cases}u+1,&u<N,\\1,&u=N,\end{cases}\qquad s(u)=\begin{cases}u-1,&u>1,\\N,&u=1.\end{cases}$$对于 ,定义
$$f_+(v,u)=\begin{cases}p(u),&p(u)\ne v,\\p(p(u)),&p(u)=v,\end{cases}$$$$f_-(v,u)=\begin{cases}s(u),&s(u)\ne v,\\s(s(u)),&s(u)=v.\end{cases}$$操作 + v 将每条 替换为 ;操作 - v 将其替换为 。
请找出一个少于 次操作的方案,或者判断无法完成转换。不要求操作次数最少。
输入格式
第一行包含一个整数 ()。
接下来 行给出初始图的邻接矩阵,再接下来 行给出目标图的邻接矩阵。
每行是一个长度为 、仅由 0 和 1 组成的字符串,不含空格。第 行第 列为 1 表示顶点 之间有边,为 0 表示没有边。
保证两个矩阵均对称,主对角线均为 0。
输出格式
如果无法转换,输出一行 -1。
否则,第一行输出整数 (),表示操作次数。接下来 行,每行输出 + v 或 - v,其中 。
任意满足要求的操作序列均可。
样例 1
输入
4
0101
1000
0001
1010
0011
0001
1000
1100
输出
2
- 1
+ 4
样例 2
输入
2
01
10
00
00
输出
-1
样例 3
输入
1
0
0
输出
0
样例解释
样例 1 中,执行 - 1 时,边 和 同时变为 和 。此时图中的边为 、、。
随后执行 + 4,边 和 同时变为 和 ,得到目标图。
样例 2 无法完成转换。样例 3 的初始图已经等于目标图。