---恢复内容开始---
题目描述
小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：
- 农场a比农场b至少多种植了c个单位的作物，
- 农场a比农场b至多多种植了c个单位的作物，
- 农场a与农场b种植的作物数一样多。
但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
输入输出格式
输入格式：第一行包括两个整数 n 和 m，分别表示农场数目和小 K 记忆中的信息数目。
接下来 m 行：
如果每行的第一个数是 1，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至少多种植了 c 个单位的作物。
如果每行的第一个数是 2，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至多多种植了 c 个单位的作物。如果每行的第一个数是 3，接下来有 2 个整数 a,b，表示农场 a 种植的的数量和 b 一样多。
输出格式：如果存在某种情况与小 K 的记忆吻合，输出“Yes”，否则输出“No”。
输入输出样例
说明
对于 100% 的数据保证：1 ≤ n，m，a，b，c ≤ 10000。
要用刚学的差分约束系统
差分约束：当n各变量x1—xn有m个约束条件形如 Xi-Xj<=Ck 这时我们可以从节点j向i连一条长度为Ck的边。建图完成后把一个点设为0，跑一遍最短路，如果存在负环则不存在解，否则dist[i]就是一组解。而如果形如Xi-Xj>=Ck 则改为跑最长路判断是否存在正环即可。
撒花结束（假装分割线
再看本题，情况1表示A-B>=C ,情况2表示A-B<=C ， 情况3表示A==B
显然建两套差分约束系统是不可行的，但是我们把1移项就会变成 B-A<=-C 所以只要在遇到1的时候把AB倒过存来再存C的相反数就行了 。情况3的话可以在读入的时候就用并查集解决
#include<iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
using namespace std;
int x,y,z,cnt,i,m,n,j,k,edge[100000],nex[100000],head[100000],ver[100000],f[10001];
long long a[10001];
bool b[1000001];
queue<int> q;
int bin(int x)
{
if(f[x]==x) return x;
f[x]=bin(f[x]);
return f[x];
}
void add(int x,int y,int z)
{
cnt+=1;
ver[cnt]=y;
nex[cnt]=head[x];
head[x]=cnt;
edge[cnt]=z;
}
bool spfa(int x)
{
memset(b,0,sizeof(b));
while(q.size()) q.pop();
q.push(x);
memset(a,0x3f,sizeof(a));
a[x]=0; b[x]=1;
while(q.size())
{
int t=q.front();
q.pop();
for(int i=head[t];i;i=nex[i])
{
int r=ver[i];
if(a[r]>a[t]+edge[i])
{
if(b[r]) return 0;
b[r]=1;
a[r]=a[t]+edge[i];
q.push(r);
}
}
}
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) f[i]=i;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&z,&x,&y);
if(z==3) f[bin(x)]=bin(y);
else
{
scanf("%d",&k);
if(z==1) add(bin(x),bin(y),-k);
if(z==2) add(bin(y),bin(x),k);
}
}
for(i=1;i<=n;i++)
if((!spfa(bin(i))))
{
printf("No");
return 0;
}
printf("Yes");
}