首页 > 代码库 > 糖果 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