Description
幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
Input
输入的第一行是两个整数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个小朋友分到的糖果；
Output
输出一行，表示lxhgww老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出-1。
Sample Input
5 7 1 1 2 2 3 2 4 4 1 3 4 5 5 4 5 2 3 5 4 5 1
Sample Output
11
HINT
【数据范围】 对于30%的数据，保证 N<=100 对于100%的数据，保证 N<=100000 对于所有的数据，保证 K<=100000，1<=X<=5，1<=A, B<=N
这是一个差分约束的题目…… 根据两两之间的关系见建图，然后跑最长路，是最长路！还有要记得判断正环…… 大概就是
len[y] = len[x] + 1;//如果x可以更新y节点 if(len[y] > n) //如果len[y] > n 则证明存在正环，把标记改为1，然后return { h = 1; return ; }全部的代码:
#include <iostream> #include <cstring> #include <cstdio> #include <queue> using namespace std; typedef long long LL; const int SZ = 500010; struct Edge { int f, t, d; }es[SZ]; int first[SZ], nxt[SZ], tot = 1, len[SZ]; int n, k; LL dis[SZ]; bool vis[SZ], h; deque < int > q; void build(int f, int t, int d) { es[++ tot] = (Edge){f, t, d}; nxt[tot] = first[f]; first[f] = tot; } void spfa(int s) { dis[s] = 0; q.push_back(s); vis[s] = 1; while(!q.empty()) { int u = q.front(); q.pop_front(); vis[u] = 0; for(int i = first[u]; i; i = nxt[i]) { int v = es[i].t; if(dis[v] < dis[u] + es[i].d) { dis[v] = dis[u] + es[i].d; len[v] = len[u] + 1; if(len[v] > n) { h = 1; return ; } if(!vis[v]) { vis[v] = 1; if(q.empty()) q.push_back(v); else v < q.front() ? q.push_front(v) : q.push_back(v); } } } } } int main() { scanf("%d%d", &n, &k); for(int i = 1; i <= k; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); if(a == 1) build(b, c, 0), build(c, b, 0); else if(a == 2) build(b, c, 1); else if(a == 3) build(c, b, 0); else if(a == 4) build(c, b, 1); else if(a == 5) build(b, c, 0); } for(int i = 1; i <= n; i ++) build(0, i, 1); spfa(0); if(h) { printf("-1"); return 0; } LL ans = 0; for(int i = 1; i <= n; i ++) ans += dis[i]; printf("%lld", ans); return 0;转载于:https://www.cnblogs.com/Loi-Vampire/p/6017054.html
