2330: [SCOI2011]糖果 Time Limit: 10 Sec Memory Limit: 128 MB 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
算法讨论：
差分约束裸题。
但是有几个注意的地方：
差分约束可以构建最短路模型，也可以构建最长路模型。
如果有x1 >= 常数。如此的形式，就提醒我们要加超级源点啦。
统计答案的方式。
为了提高SPFA的效率，可以在开始的时候把所有的点都入队。
代码：
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm> using namespace std;
const int N = 100000 + 5;
const int inf = 1000000000; int n, k, cnt;
int dis[N], head[N], que[N * 10], inque[N];
bool vis[N];
struct Edge {
int from, to, dis, next;
}edges[N << 2]; void insert(int from, int to, int d) {
++ cnt;
edges[cnt].from = from; edges[cnt].to = to; edges[cnt].dis = d;
edges[cnt].next = head[from]; head[from] = cnt;
} void init() {
int x, A, B;
scanf("%d%d", &n, &k);
for(int i = 1; i <= k; ++ i) {
scanf("%d%d%d", &x, &A, &B);
switch(x) {
case 1: { insert(A, B, 0); insert(B, A, 0); break; }
case 2: { if(A == B) puts("-1"), exit(0); insert(A, B, 1); break; }
case 3: { insert(B, A, 0); break; }
case 4: { if(A == B) puts("-1"), exit(0); insert(B, A, 1); break; }
case 5: { insert(A, B, 0); break; }
}
}
for(int i = 1; i <= n; ++ i) insert(n + 1, i, 1);
} bool spfa() {
int h = 1, t = 1;
vis[n + 1] = true; inque[n + 1] = 1;
que[h] = n + 1; dis[que[h]] = 0;
for(int i = 1; i <= n; ++ i) {
vis[i] = true;
que[++ t] = i;
inque[i] = 1;
dis[i] = -inf;
}
while(h <= t) {
int x = que[h];
vis[x] = false;
for(int i = head[x]; i; i = edges[i].next) {
int v = edges[i].to;
if(dis[v] < dis[x] + edges[i].dis) {
dis[v] = dis[x] + edges[i].dis;
if(!vis[v]) {
que[++ t] = v;
inque[v] ++;
if(inque[v] > n + 1) return false;
vis[v] = true;
}
}
}
++ h;
}
return true;
} void work() {
if(!spfa()) { puts("-1"); return; }
else {
long long ans = 0;
for(int i = 1; i <= n; ++ i)
ans = (long long) ans + dis[i];
printf("%lld\n", ans);
}
} int main() {
init();
work();
return 0;
}