基本思路：利用最短路中di≤dj+c（j指向i，边权为c，此指算法结束后）将求解三角不等式组转换为（单源）最短路问题
三角不等式（组）： xi≤xj+ck 其中xi、xj是自变量，ck是常量
差分约束系统有如下功能：
- 求不等式组的可行解
源点需要满足条件：从原点出发，一定可以走到所有的边。故可设“超级源点”
超级源点：与每一个点相连的虚拟源点
步骤：
- 先将每个不等式xi≤xj+ck转化成一条从xj走向xi，长度为ck的一条边
- 找一个超级源点，使得该院点一定可以遍历到所有边
- 从源点求一边单源最短路
结果：
- 如果存在负环，则该不等式组无解
- 如果不存在负环，则di就是原不等式组的一个可行解
当然，求最长路亦可，需将原不等式变形为xj≥xi-ck，再将最短路不等式转化为di≥dj+ck，相当于连一条从xi走向xj、长度是-ck的边
- 求不等式组解的最大值或最小值
结论：
- 如果求的是最小值，则应该求最长路（所有下界的最大值）
- 如果求的是最大值，就应该求最短路（所有上界的最小值）
问题1：如何转化xi≤c，其中c为常数？
解决1：以有向图为例利用超级源点x0，使xi≤x0+c，然后建立x0—>xi，长度是c
问题2：如何转化xi-xj=c，其中c为常数？
解决2：转换为xi-xj≤c和xi-xj≥c
代码：
//求最小值->求最长路
#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<queue>
#define _for(i,a,b) for (int i=(a);i<=(b);i++)
using namespace std;
const int N=55,M=1280;
int n,m;
int e[M],ne[M],h[N],w[M],idx;
int d[N],cnt[N];
bitset<N> vis;
inline void c_plus(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
inline void init(){
memset(h,-1,sizeof(h));
idx=0;
}
inline void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
bool spfa(){
memset(d,-1,sizeof(d));//注意：最长路
d[0]=0;
queue<int> q;
q.push(0);
vis[0]=1;
while (!q.empty()){
int now=q.front();
q.pop();
vis[now]=0;
for (int i=h[now];~i;i=ne[i]){
int j=e[i];
if (d[j]<d[now]+w[i]){//注意：最长路
d[j]=d[now]+w[i];
if (++cnt[j]>n+1){
return true;
}
if (!vis[j]){
vis[j]=1;
q.push(j);
}
}
}
}
return false;
}
int main(){
c_plus();
init();
int u,v,W,op;
cin>>n>>m;
while (m--){//op==1:<= op==2:>= op==3 =
cin>>op>>u>>v>>W;
if (op==1){
add(u,v,-W);
}else if (op==2){
add(v,u,W);
}else{
add(u,v,-W);
add(v,u,W);
}
}
_for(i,1,n){
add(0,i,0);
}
if (spfa()){
puts("NO");
}else{
_for(i,1,n){
cout<<'x'<<i<<'='<<d[i]<<endl;
}
}
return 0;
}