原题链接
题目描述：幼儿园里有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。
输入样例： 5 7 1 1 2 2 3 2 4 4 1 3 4 5 5 4 5 2 3 5 4 5 1
输出样例： 11
解析：裸裸的差分约束。 x=1，连w[u,v]=0,w[v,u]=0的两条边。 x=2，连w[u,v]=1的一条边。 x=3，连w[y,x]=0的一条边。 x=4，连w[y,x]=1的一条边。 x=5，连w[x,y]=0的一条边。 然后跑一遍最长路，若存在环，则输出-1。 最后的答案就是ans+=dis[i]。 注意：最后的答案要开longlong；0节点向各个节点连边时要逆序连，不然会超时；数组不要开小！
代码如下：
#include<cstdio> #define ll long long using namespace std; const int maxn = 100005; const int maxm = 300005; int n, k, vis[maxn], dis[maxn], tim[maxn]; int hed[maxm], nxt[maxm], to[maxm], val[maxm], cnt; ll ans; int read(void) { char c; while (c = getchar(), c < '0' || c >'9'); int x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; } void add(int x, int y, int v) { nxt[++ cnt] = hed[x]; hed[x] = cnt; to[cnt] = y; val[cnt] = v; } int dfs(int u) { vis[u] = 1; for (int i = hed[u]; i ; i = nxt[i]) { int v = to[i]; if (dis[v] < dis[u] + val[i]) { dis[v] = dis[u] + val[i]; if (vis[v] || !dfs(v)) return 0; } } vis[u] = 0; return 1; } int main() { n = read(); k = read(); for (int i = 1; i <= k; ++ i) { int opt = read(), x = read(), y = read(); if (opt == 1) add(x, y, 0), add(y, x, 0); else if (opt == 2) add(x, y, 1); else if (opt == 3) add(y, x, 0); else if (opt == 4) add(y, x, 1); else add(x, y, 0); } for (int i = n; i >= 1; -- i) add(0, i, 1); //逆序连边 if (!dfs(0)) return printf("-1"), 0; for (int i = 1; i <= n; ++ i) ans += dis[i]; printf("%lld", ans); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10229700.html
