首页 > 代码库 > 糖果 bzoj 2330
糖果 bzoj 2330
糖果（1s 128MB）candy
【题目描述】
幼儿园里有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
【数据范围】
对于30%的数据，保证 N<=100
对于100%的数据，保证 N<=100000
对于所有的数据，保证 K<=100000，1<=X<=5，1<=A, B<=N
题解：
主要算法：差分约束；最短路（Spfa）
对于题目要求的五种情况连边：
1、如果A和B一样多 —> (A, B, 0) 和 (B, A, 0)
2、如果A小于B —> (A, B, 1)
3、如果A不小于B —> (B, A, 0)
4、如果A大于B —> (B, A, 1)
5、如果A不大于B —> (A, B, 0)
无解：
1、要求某一人的糖果数大于或小于自己的 （有一条本身到本身长度不为0的边)
2、环 (一个点被访问超过n次)
附：此题超过int范围
1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdlib>
5 #include<cstdio>
6 #include<cmath>
7 using namespace std;
8 inline int Get()
9 {
10 int x = 0;
11 char c = getchar();
12 while(‘0‘ > c || c > ‘9‘) c = getchar();
13 while(‘0‘ <= c && c <= ‘9‘)
14 {
15 x = (x << 3) + (x << 1) + c - ‘0‘;
16 c = getchar();
17 }
18 return x;
19 }
20 const int me = 200233;
21 int tot;
22 int nex[me], fir[me], to[me], va[me];
23 int t, w, n, k;
24 long long ans;
25 int s[me];
26 int ue[me];
27 int len[me];
28 bool vis[me];
29 bool Same(int x, int y)
30 {
31 if(x == y)
32 {
33 printf("-1");
34 exit(0);
35 }
36 }
37 inline void Ins(int x, int y, int z)
38 {
39 nex[++tot] = fir[x];
40 fir[x] = tot;
41 to[tot] = y;
42 va[tot] = z;
43 }
44 inline bool Spfa()
45 {
46 while(t < w)
47 {
48 int u = ue[++t];
49 for(int i = fir[u]; i; i = nex[i])
50 {
51 int v = to[i];
52 if(len[v] < len[u] + va[i])
53 {
54 ++s[v];
55 if(s[v] >= n) return false;
56 len[v] = len[u] + va[i];
57 if(!vis[v])
58 {
59 vis[v] = true;
60 ue[++w] = v;
61 }
62 }
63 vis[u] = false;
64 }
65 }
66 return true;
67 }
68 int main()
69 {
70 n = Get(), k = Get();
71 for(int i = 1; i <= k; ++i)
72 {
73 int flag = Get();
74 int x = Get();
75 int y = Get();
76 if(flag == 1) Ins(x, y, 0), Ins(y, x, 0);
77 if(flag == 2) Ins(x, y, 1), Same(x, y);
78 if(flag == 3) Ins(y, x, 0);
79 if(flag == 4) Ins(y, x, 1), Same(x, y);
80 if(flag == 5) Ins(x, y, 0);
81 }
82 for(int i = 1; i <= n; ++i)
83 {
84 ue[++w] = i;
85 len[i] = 1;
86 vis[i] = true;
87 }
88 if(!Spfa())
89 {
90 printf("-1");
91 return 0;
92 }
93 for(int i = 1; i <= n; ++i)
94 ans += len[i];
95 printf("%lld", ans);
96 }
糖果 bzoj 2330