04 差数约分

问题类型

差数约分系统包含 $N$ 个变量 $x_i$ ， 以及 $M$ 个约束条件 $x_j-x_i\ge c_k$ ， $c_k$ 可以为负数，正数或者为 0

图论模型转化

使用最短路中的松弛操作去比拟约束条件，$dis[v]<dis[u]+w$
相当于约束条件中的 $x_j\ge x_i+c_k$ , 因此可以 $i$ 点向 $j$ 建一条权值为 $c_k$ 的有向边
同时引入一个 超级源点 0 点， 到每个点的有向边权值都 等于 0

最终 $x_i=dis[i]$ ， 如果存在负环， 则判定为无解

选择 $SPFA$ 算法