2330: [SCOI2011]糖果
Time Limit: 10 Sec Memory Limit: 128 MB Submit: 6692 Solved: 2226 [ ][ ][ ]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
【题解】
差分约束。
超级源点向所有边连一条权为1的边，表示至少要有一个糖果。
做最长路，求最小值。
具体见
《》
会卡SPFA，倒序从超级源点加边
网上有一个放SPFA被卡的方法：给每个点rand一个值，按值取
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #define max(a, b) ((a) > (b) ? (a) : (b)) 8 #define min(a, b) ((a) < (b) ? (a) : (b)) 9 10 inline void read(int &x) 11 { 12 x = 0;char ch = getchar(), c = ch; 13 while(ch < '0' || ch > '9')c = ch, ch = getchar(); 14 while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar(); 15 if(c == '-')x = -x; 16 } 17 18 const int INF = 0x3f3f3f3f; 19 const int MAXN = 200000 + 10; 20 const int MAXM = 200000 + 10; 21 22 struct Edge 23 { 24 int u,v,w,next; 25 Edge(int _u, int _v, int _w, int _next){u = _u;v = _v;w = _w;next = _next;} 26 Edge(){} 27 }edge[MAXM << 1]; 28 29 int n,m,head[MAXN],cnt; 30 31 inline void insert(int a, int b, int c) 32 { 33 edge[++cnt] = Edge(a, b, c, head[a]); 34 head[a] = cnt; 35 } 36 37 std::queue q; 38 int b[MAXN], d[MAXN], cntt[MAXN]; 39 40 inline int SPFA() 41 { 42 memset(cntt, 0, sizeof(cntt)); 43 memset(b, 0, sizeof(b)); 44 memset(d, -1, sizeof(d)); 45 b[0] = 1, d[0] = 0; 46 q.push(0);++cntt[0]; 47 while(q.size()) 48 { 49 int now = q.front();q.pop(); 50 b[now] = 0; 51 for(register int pos = head[now];pos;pos = edge[pos].next) 52 { 53 int v = edge[pos].v; 54 if(d[now] + edge[pos].w > d[v]) 55 { 56 d[v] = d[now] + edge[pos].w; 57 if(!b[v]) 58 { 59 q.push(v), ++ cntt[v]; 60 if(cntt[v] >= n) return 0; 61 } 62 } 63 } 64 } 65 return 1; 66 } 67 68 int main() 69 { 70 read(n), read(m); 71 register int tmp1, tmp2, tmp3; 72 for(register int i = 1;i <= m;++ i) 73 { 74 read(tmp1), read(tmp2), read(tmp3); 75 if(tmp1 == 1) 76 { 77 insert(tmp2, tmp3, 0); 78 insert(tmp3, tmp2, 0); 79 } 80 else if(tmp1 == 2) 81 { 82 if(tmp3 == tmp2) 83 { 84 printf("-1");return 0; 85 } 86 else insert(tmp2, tmp3, 1); 87 } 88 else if(tmp1 == 3) 89 insert(tmp3, tmp2, 0); 90 else if(tmp1 == 4) 91 { 92 if(tmp2 == tmp3) 93 { 94 printf("-1");return 0; 95 } 96 else insert(tmp3, tmp2, 1); 97 } 98 else if(tmp1 == 5) 99 insert(tmp2, tmp3, 0); 100 }101 for(register int i = n;i >= 1;-- i) insert(0, i, 1);102 if(SPFA())103 {104 long long ans = 0;105 for(register int i = 0;i <= n;++ i)106 ans += d[i];107 printf("%lld", ans);108 }109 else110 printf("-1");111 return 0;112 }