anyiak
立身须正,为人当明
安逸的网络日志
差分约束系统 笔记

每个约束条件$X_i-X_j≤c_k$可以变形为$X_i≤X_j+c_k$,可以把每个变量$X_i$看做有向图中的一个点,对于每个约束条件$X_i-X_j≤c_k$,从节点j到节点y连一条长度为$c_k$的有向边。再把$0$号节点和每个节点连一条长度为$0$的边。然后以0为源点求单源最短路径。则$X_i$就是d[i]。若图中有负环,则无解。

若约束条件为$X_i-X_j≥c_k$,则可变形为$X_j-X_i≤-c_k$,和上面一样。

发表评论

textsms
account_circle
email

安逸的网络日志

差分约束系统 笔记
每个约束条件$X_i-X_j≤c_k$可以变形为$X_i≤X_j+c_k$,可以把每个变量$X_i$看做有向图中的一个点,对于每个约束条件$X_i-X_j≤c_k$,从节点j到节点y连一条长度为$c_k$的有向边。再把$0$号节…
扫描二维码继续阅读
2020-12-29