今天接觸到一種很玄幻的東西： 差分約束 個人的理解：差分約束就是給定一些限制條件，求出滿足條件的最優解，或者判斷條件是否成立 做法/思路： 1.首先根據題目的條件，寫出相應的不等式 2.將不等式轉換成a-b<=c的形式 3.建一條權值為c的邊，從b指向a 4.從0點向其他點連一條邊權為1的點 5.跑 ...
今天接觸到一種很玄幻的東西：
差分約束
個人的理解：差分約束就是給定一些限制條件，求出滿足條件的最優解，或者判斷條件是否成立
做法/思路：
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
