题解：P9803 [NERC 2018] Minegraphed

· · 题解

个人认为本题的 a_{i,j}=1 应改为在由 a_{i,j}=1 的边 (i,j) 构成的有向图 G 中，i 可以到达 j。

构造思路

通过观察 CF 上 std 跑样例的输出，我们可以得到如下构造思路。

下设最底层第 i 行第 j 列的方格为 (i,j)。

如图，最底层 3n-2 列，第 i 个数在 (1,3i-2)，同时下面的列留空。

有 2n^2 行，第 2k+1 行是隔断，第 2k+2 行表示一条边。

那么高度应该设多少呢，因为表示一条边的信息量不大，5 层就足够了。

隔断的构造

对于最底层的形如 (i,3k+1) 位置而言，因为要确保 i 能经过，所以留空，其他的位置直接放障碍即可。

效果图：

边的构造

对于 a_{i,j}=0，可以直接按隔断的方式构造。

不妨设 i<j，i>j 本质一样。

设 l=3i-2,r=3j-2，对于 [l,r] 之外的列，我们把不形如 3k+1 的列全用障碍填满，这样是为了去除 i 左边，j 右边的数的影响。

同时，对于 [l,r] 内的不形如 3k+1 的列，把最底层填满即可。

然后在 l+1 堆一个障碍，l+2 堆两个障碍，然后搭一个“桥”到 r-1 即可。

效果图：