不常考的算法，但得会

本质是通过最短路的思路求解出一个 $n$ 元一次方程组的解

# 矩阵游戏

# 糖果

Trick

当差分约束中所有边都为等价关系时，设所有关系皆为 $x_i+y_i=c_i$，$x,y$ 内部之间没有连边，问 $\sum \mid x_i\mid +\mid y_i\mid$ 的最小值

考虑将这个图画出来，得到一个图，因为内部之间都没有连边，所以最后面一定能够构造出来一个二分图

成为一个二分图，也就意味着当我们对其求解得到一个生成树后，深度为奇数的点一定向偶数点连边，假设有这么一个环

![[Pasted image 20250122221308.png]]

其中 c4 为非树边，那么我们发现就有等式

$$\begin{eqnarray}x_1+y_1 &=& c_1 \
x_2+y_1 &=& c_2 \
x_2+y_2 &=& c_3 \
\end{eqnarray} \Rightarrow x_1+y_2=c_1+c_3-c_2=c_4$$
所以我们发现，这个 $c_4$ 存在的唯一意义也就成了“检测是否合法”，然后就破环为树了

我们发现这个树有一个非常好的特点，即“当你确定一个位置的值时，所有点的值也就都确定了”，所以可以考虑设一个点为根，并令其等于 $x$ ，那么我们就得到了所有点关于 $x$ 的表达式

又有一个绝对值取最小值，像 # 分金币 那样中位数定理去求就好了