将ki-1可以得到一个等于号
那么通式可以表示为
a b gt c
S[a-1]-s[a+b]<=-ki-1
a b lt c
S[a+b]-S[a-1]<=ki-1
那么根据差分约束建图,加入这些有向边
gt:
=-ki-1
lt:
=ki-1
再根据bellman_ford判断是否有无负环即可
若出现负环了则这个序列不满足所有的不等式
代码：
//212K 0MS
#include
#include
#include
using namespace std; #define maxx 105 struct edge { int u,v,w; }edge[maxx]; int n,m; int dist[maxx]; bool bellman_ford() { memset(dist,0,sizeof(dist)); for(int i=0;i
>n,n) { cin>>m; for(int i=0;i
?