spfa

之前说这个spfa已经死了，但是今天看到一道题去维护变量之间额大小关系，第一想法是并查集，但是好像并查集并不可以维护查分约束的条件，所以我看了看题解，发现是我认为已经死了的spfa
（

思想

还是松弛，还是松弛，还是松弛，其实就是一个优化的bellman ford，本质上就是bfs去找点，只要dis大就去松弛，之后看看这个点在不在队列里，如果不在就加入队列，之后一波操作完成之后就可以的到单元最短路，其实还是很easy的
上代码

void spfa(int x){
	dis[x]=0;
	vis[x]=true;
	queue<int>q;
	q.push(q);
	while(!q.empty()){
		int g=q.front();
		q.pop();
		vis[g]=flase;
		for(int i=head[g];i;i=nex[i]){
			if(dis[to[i]]>dis[g]+val[i]){
				dis[to[i]]=dis[g]+val[i];
				if(!vis[to[i]]){
					q.push(to[i]);
					vis[to[i]]=true;
				}
			}
		}
	}
}

用处----判断负环

其实这个判断主要还是在维护查分约束条件的时候去用，有些时候tarjan去找负环也是可以的而且快。

找负环的思想其实就是，可以发现，假如有负环那么是不是就会一直在这里刷最小路，所以每一个点会进入队列很多次，在没有负环的时候最多是n次，那么在这里就是只要进入了n+1次，就说明有负环
代码就是改动一下下就好

void spfa(int x){
	queue<int>q;
	q.push(x);
	dis[x]
	vis[x]=true;
	cnt[x]++; 
	while(!q.empty()){
		int g=q.front();
		q.pop();
		vis[g]=false;
		for(int i=head[g];i;i=nex[i]){
			if(dis[to[i]]>dis[g]+val[i]){
				dis[to[i]]=dis[g]+val[i];
				if(!vis[to[i]]){
					q.push(to[i]);
					vis[to[i]]=true;
					cnt[to[i]]++;
					if(cnt[to[i]]==n+1){
						cout<<"No";
						return;
					}
				}
			}
		}
	}
	cout<<"Yes";
}

维护查分约束

其实就是对于 a-b>c 我去建立a->c的边大小为-b，以此类推，对于等于关系其实就是add(a,b,0),add(b,a,0)。最后划一划就可以发现，其实有负环就说明这个条件是不合理的，为什么呢，理性的理解一下
a+b>c c+d>f
可以推出a+(b+d)>f

假如 f-(b+d+1)>a

这个条件显然是会有一个复环，并且我们发现去合并下这些不等书会出现 -1>0

显然是不合适的，所以就可以推出这个性质了，不过为了保证图的联通，我来一个超级原点n+1，他可以到达每一个点，距离为0，这样就可以去求n+1这个点的单元最短路。

代码如下

#include<bits/stdc++.h>
using namespace std;
const int maxn=5003;
int read(){
	int r=0;
	char ch;
	ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') {r=(r<<3)+(r<<1)+ch-'0';ch=getchar();}
	return r;
}


int n,m; 
int head[maxn],to[maxn],nex[maxn],val[maxn],num=0,dis[maxn];
void add(int x,int y,int z){
	to[++num]=y;
	nex[num]=head[x];
	head[x]=num;
	val[num]=z;
}

int cnt[maxn];
bool vis[maxn];
void spfa(int x){
	queue<int>q;
	q.push(x);
	dis[x]
	vis[x]=true;
	cnt[x]++; 
	while(!q.empty()){
		int g=q.front();
		q.pop();
		vis[g]=false;
		for(int i=head[g];i;i=nex[i]){
			if(dis[to[i]]>dis[g]+val[i]){
				dis[to[i]]=dis[g]+val[i];
				if(!vis[to[i]]){
					q.push(to[i]);
					vis[to[i]]=true;
					cnt[to[i]]++;
					if(cnt[to[i]]==n+1){
						cout<<"No";
						return;
					}
				}
			}
		}
	}
	cout<<"Yes";
}


int main(){
	n=read();	
	m=read();
	int a,b,c;
	for(int i=1;i<=m;i++){
		int q=read();
		if(q==1){
			a=read();b=read();c=read();
			add(a,b,-c);
		}
		if(q==2){
			a=read();b=read();c=read();
			add(b,a,c);
		}
		if(q==3){
			a=read();
			b=read();
			add(a,b,0);add(b,a,0);
		}
	}
	for(int i=1;i<=n;i++){
		add(n+1,i,0);//去避免图的不连通，所以说有一个点去作为原点
		dis[i]=maxn+1; 
	}
	spfa(n+1);
	return 0;
}