差分约束系统个人理解
2018-06-18 04:01:19来源:未知 阅读 ()
今天接触到一种很玄幻的东西:
差分约束
个人的理解:差分约束就是给定一些限制条件,求出满足条件的最优解,或者判断条件是否成立
做法/思路:
1.首先根据题目的条件,写出相应的不等式
2.将不等式转换成a-b<=c的形式
3.建一条权值为c的边,从b指向a
4.从0点向其他点连一条边权为1的点
5.跑深搜的SPFA,看看答案是否更新
这样做完,求得的是最短路!得出的是满足条件的最大值!
当然,你也可以按照和上面完全相反的思路做,
那么做法和得到的结果都是和上述完全相反的,但是都可以AC!
这里面肯定是有很多疑点的,我来根据的我理解解释一下
1.为什么要建一条从b到a的边权为c的边
因为a-b<=c,所以b到a的边权最大就是c,那么得到的答案也是最大
2.为什跑的是最短路不是最长路
因为我们每次建的都是最大的边权,而我们要求出满足所有的不等式的值。
那么当这个值是所有不等式中的最小的值得时候方能满足条件,
所以我们要求最短路
3.为什么SPFA要跑深搜而不是广搜
因为深搜容易判断负环!
4.为什么要建一条从0到所有的点的边
个人感觉:为了方便更新答案,因为0在所有边中都没有出现过
推荐几篇比较好的文章:
http://972169909-qq-com.iteye.com/blog/1185527
http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 学生信息管理系统.cpp(大二上) 2020-04-23
- C++常见编程--获取当前系统时间 2020-02-25
- Java固定资产管理系统 源码 jsp ssh 2020-01-09
- 数据结构-课程设计-职工管理系统 2020-01-02
- Linux低延迟服务器系统调优 2019-11-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash