虽然小明并没有多少钱，但是小明办了很多张银行卡，共有 n 张，以至于他自己都忘记了每张银行卡里有多少 钱了。 他只记得一些含糊的信息，这些信息主要以下列三种形式描述： 1. 银行卡a 比银行卡b 至少多c 元。 2. 银行卡a 比银行卡b 至多多c 元。 3. 银行卡a 和银行卡c 里的存款一样多。 但是由于小明的记忆有些差，他想知道是否存在一种情况，使得银行卡的存款情况和他记忆中的所有信息吻合。 输入格式: 第一行输入两个整数n 和m，分别表示银行卡数目和小明记忆中的信息的数目。(1≤n,m≤10000) 接下来 m 行： 如果每行第一个数是1，接下来有三个整数a,b,c，表示银行卡a 比银行卡b 至少多c 元。 如果每行第一个数是2，接下来有三个整数a,b,c，表示银行卡a 比银行卡b 至多多c 元。 如果每行第一个数是3，接下来有两个整数 a,b，表示银行卡a 和b 里的存款一样多。(1≤n,m,a,b,c≤10000) 输出格式: 如果存在某种情况与小明的记忆吻合，输出Yes，否则输出No。 样例输入 3 3 3 1 2 1 1 3 1 2 2 3 2 样例输出 Yes
首先讲一下差分约束系统 差分约束系统是最短路的一类经典应用。如果一个不等式组由n个变量和m个约束条件 组成，且每个约束条件都是形如 xi−xj≤k,1≤i,j≤n 的不等式，则称其为 差分约束系统 (system of difference constraints)。差分约束系统是求解一组变量的不等式组的 算法。 问题转化 我们在求解差分约束系统时，可以将其转化为图论中单源最短路（或最长路）问题。 对于不等式中的其中一组 xj−xi≤k，我们会发现它类似最短路网络（全部由最短路上 的边组成的子图）中的三角不等式 dv−du≤w<u,v>，即 du+w<u,v>≥dv，所以我们 可以理解成从顶点u 到顶点 v 连一条权值为 w<u,v> 的边，用最短路算法得到最短路 的答案 di，也就求出了原不等式组的一个解。 因此我们可以将每个变量xi作为一个顶点，对于约束条件 xj−xi≤k，连接一条边权为 k 的有向边 <i,j>。我们再增加一个超级源s，s 连向其余每个顶点，边权均为0。对这 个图执行单源最短路算法，如果程序正常结束，那么得到的最短路答案数组di 就是满 足条件的一组解；若图中存在负环，则该不等式组无解。
两种连边方法 连边有两种方法，第一种是连边后求最长路的方法，第二种是连边后求最短路 的方法。 例： xj−xi≤k 若求最短路，则变形为 xi+k≥xj，从i 到j 连一条权值为k 的边。 若求最长路，则变形为 xj−k≤xi，从j 到i 连一条权值为k 的边。 考虑到差分约束系统的边权可能为负，我们套用前面介绍的 SPFA 算法可解决这个问题。
直接上代码
#include <iostream> #include <string.h> #include <queue> using namespace std; const int MAX_M=10000; const int MAX_N=1000; const int inf=0x3f3f3f3f; int head[MAX_N]; int number_entrance[MAX_N]; int dis[MAX_N]; int inq[MAX_N]; int ans=0; int n,m; struct edge{ int w; int to; int next; }eid[MAX_M]; void insert(int u,int v,int w){ eid[ans].w=w; eid[ans].to=v; eid[ans].next=head[u]; head[u]=ans++; } int spfa(int start){ int sum=0; int totle=1; memset(inq,0, sizeof(inq)); memset(head,-1, sizeof(head)); memset(number_entrance,0, sizeof(number_entrance)); memset(dis,inf, sizeof(dis)); inq[start]=1; number_entrance[start]++; dis[start]=0; deque<int> q; q.push_back(start); while(!q.empty()){ int x=q.front();q.pop_front(); if(dis[x]*totle>sum){ q.push_back(x); continue; } //这里采用了LLL优化算法（large lable last） sum-=dis[x]; inq[x]=0; totle--; for(int i=head[x];i!=-1;i=eid[i].next){ int y=eid[i].to; if(dis[x]+eid[i].w<dis[y]){ dis[y]=dis[x]+eid[i].w; if(inq[y]==0){ number_entrance[y]++; inq[y]=1; totle++; sum+=dis[y]; if(dis[y]<dis[q.front()]){ q.push_front(y); }//这里采用了SLF优化算法（small lable first） else q.push_back(y); if(number_entrance[y]>=n) return 0; } } } } return 1; } int main() { cin>>n>>m; for(int i=1;i<=n;i++){ insert(0,i,0); insert(i,0,0); } for(int i=0;i<m;i++){ int temp; cin>>temp; if(temp==3){ int a,b; cin>>a>>b; insert(a,b,0); insert(b,a,0); } else if(temp==2){ int a,b,c; cin>>a>>b>>c; insert(a,b,-c); } else{ int a,b,c; cin>>a>>b>>c; insert(b,a,c); } } if(spfa(0)==1) cout<<"YES"; else cout<<"NO"; return 0; }这里采用的是最短路的算法，所以产生负圈的时候就直接返回0，不能产生满足方程组的变量。
• SLF：Small Label First 策略，设要加入的顶点是 j，队首元素为i，若 d[j]<d[i]，则将j 插入队首，否则插入队尾； • LLL：Large Label Last 策略，设队首元素为i，队列中所有最短距离值的 平均值为x，若 d[i]>x 则将i 插入到队尾，查找下一元素，直到找到某一顶点i 使 得 d[i]≤x，则将i 出队进行松弛操作。 • SLF 可使速度提高 15~ 20%；SLF + LLL 可提高约 50%。 在解决算法题目时，不带优化的 SPFA 就足以解决问题；而一些题目会故意制 造出让 SPFA 效率低下的数据，即使你使用这两个优化也无法避免“被卡”。 因此，SLF 和 LLL 两个优化仅作了解就可以了，在竞赛中不必使用。 对于稀疏图而言，SPFA 相比堆优化的 Dijkstra 有很大的效率提升，但是对于 稠密图而言，SPFA 最坏为 O(VE)，远差于堆优化 Dijkstra 的 O((V+E)logV)。 当然，在图中包含负权边时，SPFA 几乎是唯一的选择。因此，大家在做题时， 还是要根据数据的具体情况来判断使用哪种最短路算法。
