受力分析 Force Solution

如果我们把 $x$ 取反，会得到一个经典的差分约束形式：

我们要最小化 $x$ 的字典序，相当于最大化 $(-x_i)\leq 0$ 的字典序。（当然这一步也可以取反 $y$。）

讲讲经典的差分约束做字典序问题的方法（会了可以跳过）。

我们这个问题有一个限制是：$-x_i\leq 0\leq y_j$。所以是存在一个上界的，可以求解最大字典序。

问题可以先简化为对 $a_i\leq 0+0$ 的约束，我们对每个约束建边跑最短路。每个约束形如 $a_i+w(i,j)\geq a_j$，我们利用松弛不等式对 $i$ 到 $j$ 建边，边权为 $w(i,j)$。

跑出来的最短路，从 $0$ 到 $i$ 的最短路满足 $a_u+w(u,v)=a_v$。也就是，这条路上的每个约束都取到了上界上，导致了 $a_i$ 的值也在上界，这条路径上任何一个值 $+1$ 都会出问题。

但是我们这个问题里面有个 $y\geq 0$ 啊，和 $x\leq 0$ 的限制又不一样了！这个怎么处理？

我们知道的是 $-x$ 已然取到上界，然而最短路却有可能不经过某些 $y$，这些 $y$ 是有可能被调整的，而我们已经知道 $x$，直接把它们代进不等式，把 $y$ 调整成可取的最小值就行了。

直接写差分约束就做完了。