负环：
因为负环肯定是越跑越短的，但是一个图上所有点都选上时，肯定不是最短路。因此，我们可以通过这一点来思考怎么处理负环：
处理负环的方式只有 \(\text{SPFA}\) ，\(\text{dijkstra}\) 是不能用的。
我们在每次更新边权时，如果是正边，那么只可能对下一个答案更新一次，所以出现负环，则是对下个答案更新多次。
我们在每一次出现最短路转移时，也转移最短路包含的点的个数，则是：
if(dis[y]>dis[x]+z){
dis[y]=dis[x]+z;
cnt[y]=cnt[x]+1;//转移包含的点的个数
if(cnt[y]>=n) {flag=1;return;}//说明图中有负环,此时直接返回
if(!vis[y]){vis[y]=1; q.push(y);}
}
除了这一点，其他跟正常的四破发都一样，正常写就行了。
差分约束：
从一个问题引入：
P5960 差分约束算法
给出 \(n\) 个变量和 \(m\) 个限制条件，利用 \(x_i-x_j\leq c_k\) ，需要求出一组解，使得所有约束条件都满足。
分析：
将上方式子变形： \(x_i\leq c_k+x_j\) ，这个式子很像最短路的式子。所以我们解决这种题 先建一个超级源点 \(0\) ，将源点向每个点连一条长度为 \(0\) 的边。
之后，对于每个限制条件，从 \(j\rightarrow i\) 连一条长度为 \(c_k\) 的边，表示这个约束。
因此，一组解就是 \(0\) 点到每个点的最短路。
代码：
// P5960 【模板】差分约束算法
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int nxt[N],ver[N],tot,edge[N],head[N];
int n,m,flag=0;
int dis[N],vis[N],cnt[N];
void add(int x,int y,int z){
ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot;
}
queue<int> q;
void spfa(int x){
memset(dis,0x3f3f3f3f,sizeof(dis));
dis[x]=0,vis[x]=1;
q.push(x);
while(!q.empty()){
int x=q.front(); q.pop();
vis[x]=0;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i],z=edge[i];
if(dis[y]>dis[x]+z){
dis[y]=dis[x]+z;
cnt[y]=cnt[x]+1;
if(cnt[y]>=n+1) {flag=1;return;}//说明图中有负环
if(!vis[y]){
q.push(y); vis[y]=1;
}
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) add(0,i,0);
for(int i=1,x,y,z;i<=m;i++){
scanf("%d%d%d",&y,&x,&z);//不是正着建边
add(x,y,z);
}
spfa(0);
if(flag==1) puts("NO");
else for(int i=1;i<=n;i++) printf("%d ",dis[i]); puts("");
system("pause");
return 0;
}
这样，我们发现，通过建边求最短路的形式，能使这些式子同时得到满足，这样就叫差分约束系统。
建边方式：
这里的 \(z\) 都是非负数：
-
\(y-x \leq z\) ，那么这样是在求最短路，可以这么理解：\(x,y\) 已经求出了最短路，那么最短路之差肯定不会比两点之间路径长。
如果相等，说明最短路就是这条路。又因为路长为 \(dis[y]-dis[x]\) ，说明这条边是从 \(x\rightarrow y\) 的边权为 \(z\) 的有向边。 -
\(y-x \geq z\) ，那么是在求最长路，和上面一样，两点的最长路之差不会比两点路径长。边也是从 \(x\rightarrow y\) 边权为 \(z\) 的有向边。
-
\(x-y=z\) ，拆成两个约束条件，即：\(x\rightarrow y\)，边权为 \(0\)，\(y\rightarrow x\) ，边权为 \(0\)。
要注意连边的顺序，写多了就好理解了。
判断是否成立：
差分约束判断条件是否能够全部成立的方法就是 判断负环 。但是要注意：我们因为添加了一个超级源点，所以 负环的标准是有 \(n+1\) 个点，这里要注意。
建立超级源点：
对于一些题目，超级源点到其他点的边权也不同。有的要求必须有，就建边权为最小限制的点。否则，就建立边权为零的点。
例题：
[SCOI2011]糖果
题意：
给你五种操作，每个操作给定两两点关于权值的限制关系，求权值之和。
分析：
很明显，这道题限制了点之间的大小关系，因此很容易想到差分约束。
首先超级源点到其他点建立一条权值为 \(1\) 的路径。因为每个小朋友必须有。
看式子，发现都是 \(y-x \geq z\) 类型的式子，因此是求最长路。
注意判断一下负环即可，建边方式自己列一下不等式，建一下即可。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6e5+5;
int nxt[N],ver[N],tot,edge[N],head[N];
int n,m,flag=0,ans;
int dis[N],vis[N],cnt[N];
void add(int x,int y,int z){
ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot;
}
queue<int> q;
signed main(){
cin>>n>>m;
for(int i=1,op,x,y;i<=m;i++){
scanf("%lld%lld%lld",&op,&x,&y);
if((op==2||op==4)&&(x==y)) flag=1;
if(op==1) add(x,y,0),add(y,x,0);
else if(op==2) add(x,y,1);
else if(op==3) add(y,x,0);
else if(op==4) add(y,x,1);
else if(op==5) add(x,y,0);
}
if(flag==1){puts("-1");return 0;}
for(int i=n;i>=1;i--) add(0,i,1);
dis[0]=0,vis[0]=1;
q.push(0);
while(!q.empty()){
int x=q.front(); q.pop();
vis[x]=0;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i],z=edge[i];
if(dis[y]<dis[x]+z){
cnt[y]=cnt[x]+1;
dis[y]=dis[x]+z;
if(cnt[y]==n+1){puts("-1");return 0;}
if(!vis[y]){
q.push(y); vis[y]=1;
}
}
}
}
for(int i=1;i<=n;i++) ans+=dis[i];
cout<<ans<<endl;
system("pause");
return 0;
}