P11832 [省选联考 2025] 图排列 题解 最后更新于 2025-05-02 00:29:23

谨以此题解纪念我的省选联考。 还没写代码，如有问题可以在评论区提出。 首先题意可以转化为把所有节点按某种顺序排成一列，使得点之间的边两两不交，注意这里的相交指的是类似平面图一样把所有边都画到节点的上面时两两不交。 先考虑树怎么做，不难发现我们一定能令第一个点为一号点，接着考虑一个合法排列方案最后的形态，一定是每棵子树占据一部分连续的编号，故你可以把每棵子树递归下去做，然后再按照对应排列的最前面节点的大小关系把这些排列合并，注意你合并完后，加入根节点时实际上是可以将其加入到任意相邻两个子树之间的。 接着考虑森林，我们可以按照上述方法预处理出每棵树的最优排列，考察一下森林的最终形态不难发现最后一定是先按照某棵树的最优排列排，然后插入一整棵树，插入的树里相邻两个节点还可以插入其他树，但是要继续放上一棵必须得等到这一棵及其连带全部插入完，树之间形成了一个树形结构，直接模拟即可获得 52 分。 若是联通块有环呢？对于联通块之间的合并我们仍可以采用上述方法，现在问题是有环或者是类似仙人掌的一些奇怪的东西怎么办，对于环，可以发现它只有两种排列方式，即最小编号节点作为起点，剩下的逆时针或者顺时针遍历。对于其他东西我们先缩点双，一个点双联通分量内部和环是一样的，只不过要考虑一下父亲圆点带来的限制，不过遍历顺序也只有两种。 于是对于有环的连通块，我们先缩点双，然后考虑对于一个方点，其遍历顺序就是从父亲圆点开始顺时针或者逆时针沿环遍历，可以在中途插入对应圆点的子树的排列，圆点就是有点类似森林地合并各个方点。 于是问题最后变成了我们怎样对于一个方点找到它对应的“环”，有两种方法，一中是考虑耳分解，每次对于出去的耳调整一下环形态，不难发现耳直接搜是一定能有解的，不然会出现一个类似杏仁的东西，然后整个图就无解了。 还有一种方法是考虑从这个类似环的东西的最底层开始缩，即每次类似广义串并联图一样缩二度点，然后将其插入两边节点的链表里，表示遍历完就立刻遍历，最后也能得到一个环，代码可能需要注意一些细节，不要写成平方了。 upd：保证正确性，之前那句话是叠甲用的/wul，不写了不写了，求管理通过。