赛时没有过又为队友拖后腿了。
考虑原限制具有什么性质，可以发现 \(j\) 能接到 \(i\) 后面仅当 \(\text{max}_{S_{i}} \leqslant \text{max}_{S_{j}}\)，而当 \(\text{max}_{S_{i}} = \text{max}_{S_{j}}\) 时 \(j\) 必然能接到 \(i\) 后面。如果说 \(\text{max}_{S_{i}}\) 都互不相同，那么这个就是一个非常经典的 \(\text{DAG}\) 最小链覆盖问题，直接网络流即可解决。
之前一个非常 \(\text{trivial}\) 的想法是所有 \(\text{max}_{S_{i}}\) 相同的都连在一起，但其实是很好 \(\text{hack}\) 的，因为 \(\text{max}_{S_{i}}\) 可以分裂来凑新的链导致并成一团其实不优。但可以注意到一个非常关键的事情是其实原图是比较贴近于 \(\text{DAG}\) 的，考虑直接在原图上跑会发生什么，不难发现这样答案就一定为 \(\text{n}\) 了，因为每一个点都可以连向 \(\text{max}_{S_{i}}\) 与自己相同的，但其实这样会构成环。但这一启发我们可以考虑如果连成了环看看其是否能够调整为一个合法的解。
实际上绝大部分的环都是可以调整的，令 \(c\) 表示 \(\text{max}_{S_{i}}=d\) 的点的个数，那么如果环长本来就为 \(c\)，这个显然是不能调整的，所以我们限制环的长度在 \([0,c-1]\) 范围之内，令连向 \(d\) 的和连出 \(d\) 的个数分别为 \(x,y\)，令环长为 \(z\)，可以发现网络流本身的性质就满足了 \(z\leqslant \text{min}(c-x,c-y)\)，而出边的匹配是可以自由调整的，所以我们让出边所涉及的点尽量与入边所涉及的点尽量有交即可让入边出边集合并刚好为 \(\text{max}(x,y)\)，我们令集合并内的点是关键的，外的为非关键的。容易发现根据上述讨论，关键点的个数几乎是 \(>0\) 的，违反的是一个平凡的 \(\text{case}\) 即 \(x=y=0,z\leqslant c-1\) 的情况，但这样直接将所有非关键点连成一条链即可。实际上可以将非关键点事先连成一条链，这样可达到 \(z-1\)，只要再多 \(1\) 即可，注意到内部所有点的出边集合都是一样的，可以将其中一个关键点的一条出边直接断裂，在内部将链直接插入即可，特别的如果关键点没有出边，则直接将链接在它们后面即可。综上所述，所有在 \([0,c-1]\) 范围内的环都可以调整为链。
所以我们可以建以 \(\text{max}_{S_{i}}\) 为节点的 \(\text{DAG}\) 最小链覆盖模型，由于每一个 \(S_{i}\) 只能用一次，中间还要建一排以 \(S_{i}\) 为节点的中转节点，需要限制每一个 \(\text{max}_{S_{i}}\) 的入流与出流不超过 \(c\)，\(\text{max}_{S_{i}}\) 入流连向出流自己不超过 \(c-1\)，而每一个中转节点只能用一次。
跑完网络流后按上述过程构造方案即可做到 \(O(m\sqrt n)\)。
- Universal Shenyang Stage The 2nduniversal stage the 2nd universal shenyang stage the universal qingdao stage the universal binjiang stage the universal okayama stage the universal stage hefei the universal taipei stage the universal stage 6555 good universal contest nanjing stage universal shaanxi stage 6735