题意就是给出每段至少有几个数如ai到bi至少用ci个数....问整个集合至少需要多少个数才能满足所有的条件...ci <= bi - a1 + 1...
转化一下...Sk代表不大于k有多少个数...那么题目的条件就转化为一组 Sbi - S(ai-1) >= ci了..
分析题目给出的不等式...以及题目的"至少需要"..也就是要求的是一组最小非负解...
传统的用SPFA解差分约束..是给出的一组或者说要化成一组 a - b <= k 的形式...然后来构边.. a为终点,b为起点..权值为k...用SPFA求出的是确定一个数后的最大解..
但这道题是要求的是最小解...这里就要更加的深入理解用SPFA解差分约束了..
之所以能用SPFA来解差分约束...就是SPFA在relax时是
d [ line.end ] >= d [ line.start ] + line.wight
更新完后..所有的 d [ i ] 都会满足这个条件..
再看差分约束系统每一项的形式
a - b <= k 稍微转化一下..
就是 b>=a-k ...
如果把 b作为 line.end..a作为 line.start..k作为line.wight...那么就和SPFA的relax一模一样...
SPFA作完后能保证所有的 d [ line.end ] >= d [ line.start ] + line.wight ...自然就能保证所有的不等式成立...
所以将每一项的 b 作为线段的终点,a作为线段的起点,k作为线段的权值...定一个源点(相当于给某一个点一个确定值)然后做一次SPFA..就能得到一组满足所有条件的解(这里不讨论存在负环的情况)...并且这个解是确定了某个值后的最大一组解( 所有的和相加最大...这里还没理解...)..
回到这道题...给出的每一项是 a - b >=k 可以将两边同时乘负一得到 b - a <= -k 也可以干脆就把 SPFA 的Relax 改成d [ line.end ] <= d [ line.start ] + line.wight 来求解...因为同理a - b >=k 可以写成 b <= a + k....同样的b 作为线段的终点,a作为线段的起点,k作为线段的权值
我是用的后面一种方法...SPFA的Relax改了以后~~做出的一组解首先会是满足所有约束条件的...并且这组解是在确定了某个点的值下最小的一组解(和原始的那种正好相反)...这道题肯定就是把最小的点赋值为0然后来求..做出来直接就是题目所要求一组最小的非负解了...答案也就是在 d [ maxdata ] 里...
这道题有两个隐性条件一定要用上...第一个就是 Sk - S(k-1) >=0 相邻两个数的差是大于等于0的...Sk - S(k-1) <=1 相邻两个数的差是小于等于1的...要加上这些约束条件..也就是加上这些边..
题目的处理的方面...因为题目的数列是从0开始的...但在沟成约束条件是...如输入告诉说 1 到 3 至少有1个数..那转化成不等式应该是 S3 - S0 >=1...那如果给出的是 0 到 3 至少有一个数呢??难道 S3 - S-1 >=1 ??明显下标越界..所以干脆把数列向右平移一个单位..让其从1开始就行了...还有一点就是我在程序中用minnum和maxnum分别记录这组约束条件中出现的最小数和最小数,减少不必要的操作...
Runtime error的...要注意边的个数..不止题目给的50000...因为自己要构更多的边...就是那两个隐形条件的边...所以至少需要开150001的大小..
Progarm:
分享到:
相关推荐
北大POJ1201-Intervals 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ2002-Squares 解题报告+AC代码
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
POJ3211--Washing Clothes
北大POJ3414-Pots 解题报告+AC代码
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1716-Integer Intervals【Difference Constraints】 解题报告+AC代码
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
北大POJ1159-Palindrome 解题报告+AC代码
poj 1000-3000部分代码 网上收集
北大POJ1159-Palindrome
北大POJ1837-Balance
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码