差分约束系统总结(转)转载地址
差分约束总结:
今天请教了DQS大神,算是对差分做一个系统性的总结吧,也算是对自己近期不完善理解的差分约束理一遍。
差分约束分为3大类,求最小,求最大,求是否满足约束
[luoguP3275] [SCOI2011]糖果(差分约束)传送门
差分约束裸题
但是坑!
有一个点是长为10W的链,需要逆序加边才能过(真是玄学)
还有各种坑爹数据
开longlong
——代码
1 #include <cstdio>
2 #include <cstring>
[luoguP1993] 小 K 的农场(差分约束 + spfa 判断负环)传送门
差分约束系统。。找负环用spfa就行
——代码
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #define N 100001
5
6 int n, m, cnt









