题意：FJ的N头牛要按编号排成一行，有的牛a和牛b关系好，距离不能超过c，有的牛a和牛b关系不好，距离至少要为c，求牛1到牛n的最大距离

题解：

差分约束spfa

满足不等式：

d[i+1]-d[i]>=0 -> d[i]-d[i+1]<=0

d[j]-d[i]<=c     -> d[j]-d[i]<=c   

d[j]-d[i]>=c     -> d[i]-d[j]<=-c

求d[t]-d[s]的最大值

由于是求最大值，所以用最短路求解，按照上述不等式连边即可

 

总结：求解差分约束系统的一般思路

1、先找出要求的量的关系，确定最短路还是最长路

2、确定求什么后将条件给出的式子化成要求的那一种

对于差分不等式，a - b <= c ，建一条 b 到 a 的权值为 c 的边，求的是最短路，得到的是最大值（本题求的就是最大值），对于不等式 a - b >= c ，建一条 b 到 a 的权值为 c 的边，求的是最长路，得到的是最小值。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll long longusing namespace std;const int N = 1010;const int M = 20010;int n,n1,n2,e_num;int nxt[M],to[M],w[M],h[N],cnt[N];ll inf=1ll<<60,dis[N];bool in[N];queue
            
              q;int gi() { int x=0,o=1; char ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}void add(int x, int y, int z) { nxt[++e_num]=h[x],to[e_num]=y,w[e_num]=z,h[x]=e_num;}bool spfa() { for(int i=1; i<=n; i++) dis[i]=inf; dis[1]=0,in[1]=0,q.push(1); while(!q.empty()) { int u=q.front(); in[u]=0,q.pop(); for(int i=h[u]; i; i=nxt[i]) { int v=to[i]; if(dis[u]+w[i]
             
              n) return false; } } } } return true;}int main() { n=gi(),n1=gi(),n2=gi(); for(int i=1; i<=n1; i++) { int x=gi(),y=gi(),z=gi(); add(x,y,z); } for(int i=1; i<=n2; i++) { int x=gi(),y=gi(),z=gi(); add(y,x,-z); } for(int i=1; i