BZOJ 3436 小K的农场

题目大意

给你一个数列和一些限定关系，求是否存在一种分配情况满足所有关系。

差分约束裸题。

注意两点。

1. SPFA()判负环的时候注意要把所有点都最早撇到队列里……这样的话就会规避非联通图的这一特殊情况。
2. 最长路/最短路是取决于具体情况的。并非一定用最长/最短路（我喜欢最短路但是该用啥用啥也不能强制）。

对于一个图进行查询（搜索，最短路）的时候一定要记得看一下是否搜索完全，图可能不联通。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,mode,inx,iny,inz,dis[10010],cnt[10010];
int to[100010],nex[100010],val[100010],head[10010],tot;
bool inq[10010];
queue<int>q;
void addedge(int tx,int ty,int tz){to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;}
bool spfa()
{
	for(int i=n;i;--i) q.push(i);
	memset(dis,0x3f,sizeof dis);
	memset(inq,true,sizeof inq);
	dis[1]=0;
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		inq[tmp]=false;
		for(int i=head[tmp];i;i=nex[i])
			if(dis[to[i]]>dis[tmp]+val[i])
			{
				dis[to[i]]=dis[tmp]+val[i];
				if(!inq[to[i]])
				{
					cnt[to[i]]++;
					if(cnt[to[i]]>=n) return false;
					inq[to[i]]=true;
					q.push(to[i]);
				}
			}
	}
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d",&mode);
		switch(mode)
		{
			case 1: scanf("%d%d%d",&inx,&iny,&inz),addedge(inx,iny,-inz);break;
			case 2: scanf("%d%d%d",&inx,&iny,&inz),addedge(iny,inx,inz);break;
			case 3: scanf("%d%d",&inx,&iny),addedge(inx,iny,0),addedge(iny,inx,0);break;
		}
	}
	printf("%s\n",spfa()?"Yes":"No");
	return 0;
}