bzoj 2330 [SCOI2011]糖果

Posted by

题目链接

http://www.lydsy.com/JudgeOnline/problem.php?id=2330

题解

差分约束系统

给出有$ n$个变量和$m$个约束条件(形如$ a_i-a_j\leq k$的不等式)的系统,求出满足这些约束条件的一组变量。
思路是把数的模型转换成图的模型。
当有$ a_i-a_j\leq k$这个条件时,即在图中创建一条从$ a_j$指向$ a_i$的有向边,设置边权为$ k$。
然而还要创建一个起点,类似于网络流中的源点,它连向每一个点,边权均为$ 0$。
最后执行单源最短路算法,求得$ {d_i}$为答案。
此题为模板题,不等式取等时创建边权为$ 0$的边,不取等时创建边权为$ 1$的边。
另外有一个玄学优化:数据中存在一条长十万的长链,给起点加边的时候需要从$ n$到$ 1$加边……
另外图中存在环,需要记录进队次数判环。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注