一般常用SPFA
对于求最大值
当然要跑最短路
每个不等式转化为a-b<=x
连边b->a,val=x
dis[a]>dis[b]+x才能松弛为
dis[a]<=dis[b]+x
当求最小值时
就跑最长路
每个不等式转化为a-b>=x
连边b->a,val=x
dis[a]<dis[b]+x才能松弛为
dis[a]>=dis[b]+x
若a-b<x或a-b>x
转化为a-b<=x-1或a-b>=x+1
若a=b
连边a->b,val=0,b->a,val=0
注意判断正负环（无解），无法到达（无限解）
一些区间内树的数量必须大于某个值，问1到n最少要中多少树。sum[r]-sum[l-1]>=x，连边(l-1,r)=x，同时0<=sum[i]-sum[i-1]<=1，连边(i-1,i)=0，连边(i+1,i)=-1，之后跑最长路即可。
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a-1,b,c);
}
for(int i=0;i<=n;i++){
if(i)add(i-1,i,0);
add(i+1,i,-1);
}
spfa(0);
cout<<dis[n];
一些牛希望和某个牛距离不超过某个数，和某个牛不小于某个数，求满足条件的1号到n号之间的距离。由于是在数轴上且从1到n排列，两头相邻的牛之间也要连边，从超级源点开始判断无解，再从1开始计算答案。
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
for(int i=1;i<=k;i++){
int a,b,c;
cin>>a>>b>>c;
add(b,a,-c);
}
for(int i=1;i<n;i++)add(i+1,i,0);
for(int i=1;i<=n;i++)add(0,i,0);
int re=spfa(0);
if(re<0)return cout<<re,0;
else cout<<spfa(1);
一段给出一些区间内的sum，判断这些区间是否合法。注意源点不确定的情况，需要为每个没有跑spfa的点跑一遍spfa，连边时由于是区间和，不是不等式，所以需要双向连边。
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
add(b,a-1,-c);
add(a-1,b,c);
}
bool flag=true;
for(int i=0;i<=n;i++){
if(num[i]==0&&spfa(i)==false){
flag=false;
break;
}
}
有1g，2g，3g三种砝码，去除a和b两个放到左盘，另选两个放到右盘，问左盘大于、等于、小于右盘的选法，只有结果保证唯一才计入答案。对于a+b与c+d的关系，可以转化为a-c与d-b的关系，于是记录i-j的最大值和最小值，分别跑最短路求上界和最长路求下届，之后暴力枚举c和d进行判断，若min(a-c)>max(d-b)则左盘一定大于右盘，其余类似。
for(int i=1;i<=n;i++){
string s;
cin>>s;
for(int j=0;j<s.size();j++){
if(s.at(j)=='+')ma[i][j+1]=2,mi[i][j+1]=1;
else if(s.at(j)=='-')ma[i][j+1]=-1,mi[i][j+1]=-2;
else if(s.at(j)=='?')ma[i][j+1]=2,mi[i][j+1]=-2;
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
if(i==k)continue;
for(int j=1;j<=n;j++){
if(i==j||j==k)continue;
ma[i][j]=min(ma[i][j],ma[i][k]+ma[k][j]);
mi[i][j]=max(mi[i][j],mi[i][k]+mi[k][j]);
}
}
}
static int c1,c2,c3;
for(int i=1;i<=n;i++){
if(i==a||i==b)continue;
for(int j=1;j<i;j++){
if(j==a||j==b)continue;
c1+=mi[a][i]>ma[j][b]||mi[b][i]>ma[j][a];
c3+=mi[i][a]>ma[b][j]||mi[i][b]>ma[a][j];
c2+=((mi[a][i]==ma[a][i]&&mi[j][b]==ma[j][b]&&mi[a][i]==mi[j][b])||(mi[a][j]==ma[a][j]&&mi[i][b]==ma[i][b]&&mi[a][j]==mi[i][b]));
}
}