poj 1364 King(差分约束)(中等) - c++编程基础

将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
      
       ?

poj 1364 King(差分约束)(中等)(二)