受力分析 Force Solution
Comentropy
·
·
题解
如果我们把 x 取反，会得到一个经典的差分约束形式：
\begin{aligned}
&l_{i,j}\leq -(-x_i)+y_j\leq r_{i,j}\\
&\begin{cases}
&(-x_i)\leq y_j-l_{i,j}\\
&y_{j}-r_{i,j}\leq (-x_i)
\end{cases}
\end{aligned}
我们要最小化 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 调整成可取的最小值就行了。
直接写差分约束就做完了。