题目链接：
https://www.lydsy.com/JudgeOnline/problem.php?id=2330
题目大意：
幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
输入的第一行是两个整数N，K。
接下来K行，表示这些点需要满足的关系，每行3个数字，X，A，B。
如果X=1， 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多；
如果X=2， 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果；
如果X=3， 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果；
如果X=4， 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果；
如果X=5， 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果；
输出一行，表示lxhgww老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出-1。
思路：
差分约束系统求最小值，要用最长路。
差分约束系统求最大值时，构造边按照：d[v] - d[u] <= Edge[u][v] (u->v连边)，求解时按照最短路求解（也就是松弛的时候按照原来的方式进行松弛）
求最小值时，构造边按照：d[v] - d[u] >= Edge[u][v]（u->v连边），求解时按照最长路进行求解（松弛的时候和原来相反）
坑：
添加边的时候需要逆序添加，数据原因。（也可以将要添加的边存起来，随机一下添加）
需要特判自环的情况不然也会T
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);//不可再使用scanf printf
#define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Mem(a) memset(a, 0, sizeof(a))
#define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))
#define MID(l, r) ((l) + ((r) - (l)) / 2)
#define lson ((o)<<1)
#define rson ((o)<<1|1)
#define Accepted 0
#pragma comment(linker, "/STACK:102400000,102400000")//栈外挂
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
typedef long long ll;
const int maxn = + ;
const int MOD = ;//const引用更快，宏定义也更快
const ll INF = 1e12 + ;
const double eps = 1e-; struct edge
{
ll u, v;
ll w;
ll next;
};
edge a[maxn];
ll head[maxn], node;
void addedge(ll u, ll v, ll w)
{
a[node].u = u;
a[node].v = v;
a[node].w = w;
a[node].next = head[u];
head[u] = node++;
} ll cnt[maxn];
bool vis[maxn];
ll d[maxn];
ll n;
bool SPFA(ll u)
{
queue<ll>q;
memset(vis, , sizeof(vis));
memset(cnt, , sizeof(cnt));
for(int i = ; i <= n; i++)d[i] = -INF;//赋值成最小值 来求解最长路
d[u] = ;
vis[u] = ;
q.push(u);
while(!q.empty())
{
ll u = q.front();
q.pop();
vis[u] = ;
for(ll i = head[u]; i != -; i = a[i].next)
{
edge& e = a[i];
if(d[e.v] < d[u] + e.w)//求最长路松弛符号改变
{
d[e.v] = d[u] + e.w;
if(!vis[e.v])
{
q.push(e.v);
vis[e.v] = ;
if(++cnt[e.v] >= n)return false;
}
}
}
}
return true;
}
int main()
{
memset(head, -, sizeof(head));
ll k, x, a, b;
scanf("%lld%lld", &n, &k);
for(ll i = n; i >= ; i--)addedge(, i, );
bool flag = ;
while(k--)
{
scanf("%lld%lld%lld", &x, &a, &b);
if(x == )
{
addedge(a, b, );
addedge(b, a, );
}
else if(x == )
{
if(a == b)flag = ;
addedge(a, b, );
}
else if(x == )
{
addedge(b, a, );
}
else if(x == )
{
if(a == b)flag = ;
addedge(b, a, );
}
else
{
addedge(a, b, );
}
}
if(!flag && SPFA())
{
ll ans = ;
for(ll i = ; i <= n; i++)ans += d[i] + ;//加上最开始的1
printf("%lld\n", ans);
}
else
{
printf("-1\n");
}
return Accepted;
}