OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SCOI2011】糖果

【题目描述】

幼儿园里有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

【题解】

五种关系对应五种等式或不等式:

①A=B;②A<B;③A>=B;④A>B;⑤A<=B

变形后得到:

①A>=B,B>=A;②B>=A+1;③A>=B;④A>=B+1;⑤B>=A

根据差分约束系统的性质建图,跑单源最长路即可。注意初始化的时候每个点的最长路标记为1,这样根据差分约束系统的性质求出来的可行解就是每个点都不小于1的最小解,相加就是最后的答案。

遇到条件②和④,如果A和B相等就立即输出-1,要不然会被卡0.0

还有,答案记得开64位整数……这幼儿园太壕伤不起……

【代码】

调了半天才过……貌似标程各种SCC缩点+DP,但实际上数据比较弱……

http://paste.ubuntu.com/8687505/

评论

© OI技术宅 | Powered by LOFTER