Mato is No.1

i    ：  0   1   2   3   4
D[i]：  2   4   3   2   \
M[i]： 1   2   6  14   \
S[i]：  0  3   7  10  16
可以發現，D[0]值減小1之后，S[1..3]的值都減小了1，而S[4]的值不變。這是因為在D[0]減小1之前，對于1<=i<3均有S[i]>M[i]，D[0]若減小1，顯然S[1]會減小1，而由于S[1]>M[1]，S[1]=max{S[1], M[1]}，所以S[1]的值減小1會使得max{S[1], M[1]}減小1，從而S[2]的值減小1，然后由于初始的S[2]>M[2]，同樣會使得S[3]減小1，而初始的S[3]<=M[3]，故S[3]減小1不會使得max{S[3], M[3]}發生變化，所以S[4]的值不會受到影響。
所以，可以得到：D[i]減小1，會使得S[i+1..j+1]均減小1，其中j是使任意i+1<=k<=j0均滿足S[k]（減小前）>M[k]的最大的j0值。
從這個當中可以發現，對于原題的每一個可行方案，必然都是分為若干個階段，其中每一階段是將某個D[i]值減小1（當然，要滿足D[i]在減小前>0），每一階段進行后都會將從S[i+1]開始的連續的一段S值都減小1，恰好可以抽象成一條連續的路徑，又因為當S[i]減小到<=M[i]的時候就必須停止了（準確來說是不能再往后延伸了），所以每個S[i]的能夠繼續延伸的減小的量都是有限的，為初始的S[i]-M[i]（如果這個值<0，則取0），剛好是一個上限。這很明顯是增廣路思想。
所以，經過整理，可以建立一個網絡流模型：
<1>設立兩個源點s和s'（其中s是真正的源點）及匯點t，連邊<s, s'>，容量為K，費用為0，表示最多只能有K個階段；
<2>將每一站i拆成兩個點i'和i''，連邊<i', i''>，容量為max(S[i]-M[i], 0)，費用為0，表示該點最多只能接受max(S[i]-M[i], 0)次加速器作用；
<3>對于所有的i滿足1<=i<N，連邊<(i-1)'', i'>，容量為INF，費用為第i站下車的人數（這是因為即使S[i]<=M[i]，加速器對于本站仍然有效，只是不能繼續延伸，所以表示加速器起的效果的邊應該在本站的限制之前）；
<4>對于所有的i滿足0<=i<N-1，連邊<s', i''>，容量為初始D[i]，費用為0，表示使用加速器的地方，從下一站開始對S[i]起效果；
<5>對于所有的i滿足1<=i<N，連邊<i', t>，容量為INF，費用為0，表示加速器作用的結束。
（其實，0'和(N-1)''這兩個點是木有任何意義的，可以從圖中刪掉）
這樣，每一階段加速器的作用都可以表示為一條從s到t的增廣路，該網絡流模型中的各種限制也反應了題目中的限制。對該網絡求最大費用最大流，得到的總的最大費用從初始的總旅行時間中減去（注意總旅行時間是long long的），即為答案。可以證明，這個模型符合“兩條原則”，所以是正確的。

（2）流量平衡思想：
這個思想的應用非常廣，可以解釋絕大多數網絡流模型。
所謂流量平衡，就是指在一個可行流里，除了源點和匯點外，其余每個點的入邊流量總和都等于出邊流量總和。可以證明，一個流是可行流當且僅當其：（1）每條邊的流量都不超過容量限制；（2）符合流量平衡。
流量平衡思想的主要用處是：可以把圖中的每條邊的流量（當然必須是非負的）都想像為一個變量的值，對于每個點，滿足流量平衡，也就是一些變量的和值滿足某種等量關系，如果這些等量關系剛好能夠反映題目中的所有信息，邊的容量限制也反映題目中的條件，且這個模型符合“兩條原則”，則該模型就是正確的了。在建模的時候，應先單獨考慮各個點，找到它們的所有入邊和出邊代表的變量是什么，然后再將這些邊合并，構成圖。
在用流量平衡建模時有一些技巧：
<1>要注意每條邊都同時作為一個點的出邊和一個點的入邊，因此，每個變量必然同時關聯兩個等量關系，且分別出現在這兩個等量關系的等號的左邊和右邊（或者是以一對相反數形式出現）；
<2>如果題目中給出的變量和值關系不是等量關系，而是不等關系，那么可以將剩余的流量通過從源點或往匯點連邊的辦法，使其平衡。比如，若題目中有y1+y2>=x1+x2>=y1+y2-5這樣的關系，則可以這樣做：設置一個點，將y1、y2代表的邊作為該點的入邊，將x1、x2代表的邊作為該點的出邊，然后從該點往匯點連一條容量為5的邊；
<3>如果點內部有限制（比如某個點自身的權值不能超過X等等），那么該點內部也“暗含”一個變量，此時就需要拆點（不一定拆成兩個點，可能拆成更多的點），然后在拆出的點當中再連邊，附加一些限制，然后再考慮流量平衡；
<4>如果一條邊有上下界，且上下界相等（也就是該邊的流量已經定死了），則可以改裝成費用流，將這條邊的費用設為一個絕對值很大的負數，這樣就肯定能保證該邊滿流了。
例2：餐巾計劃問題（經典問題）
這個的模型用增廣路思想根本就不能解釋。其實，可以用增廣路思想建立一個模型，但是是錯誤的，可以用下面的“兩條原則”檢查出來。
<1>對于每天，要處理的餐巾總數=當天買的餐巾總數+當天洗好的餐巾總數+上一天保留下來的未處理的餐巾總數，這三個當作入邊；
<2>對于每天，要處理的餐巾總數=送快洗部的餐巾總數+送慢洗部的餐巾總數+保存起來留到下一天處理的餐巾總數，這三個都當作出邊；
<3>每天的內部有限制：要用的餐巾總數>=當天的需求量，其實，總可以構造出要用的餐巾總數=當天的需求量的最優方案，所以這些限制其實是上下界相等的。
而<1>和<2>剛好描述了每天這個整體的流量平衡，<3>是一個內部限制，用拆點解決。仔細觀察所有的邊可以發現，“當天洗好的餐巾總數”與“送快洗部的餐巾總數”和“送慢洗部的餐巾總數”可以合并，“上一天保留下來的未處理的餐巾總數”與“保存起來留到下一天處理的餐巾總數”也可以合并。
這樣，可以構造出兩種模型：
1)：第i天拆成兩個點i'和i''，連邊<i', i''>，容量為第i天需求量，費用為0；對于任意0<=i<N-1，連邊<i'', (i+1)''>，容量INF，費用0；對于任意0<=i<N，連邊<S, i'>，容量INF，費用p，連邊<i'', T>，容量INF，費用0；對于任意0<=i<N-m，連邊<i'', (i+m)'>，容量INF，費用f；對于任意0<=i<N-n，連邊<i'', (i+n)'>，容量INF，費用s；求最小費用最大流，最小的總費用就是結果；
2)：第i天拆成兩個點i'和i''，連邊<S, i''>和<i', T>，容量均為第i天需求量，費用均為0；對于任意0<=i<N-1，連邊<i'', (i+1)''>，容量INF，費用0；對于任意0<=i<N，連邊<S, i'>，容量INF，費用p；對于任意0<=i<N-m，連邊<i'', (i+m)'>，容量INF，費用f；對于任意0<=i<N-n，連邊<i'', (i+n)'>，容量INF，費用s；求最小費用最大流，最小的總費用就是結果。
以上兩種模型，看上去都符合題目中的限制，也符合流量平衡，但是，模型1)是錯誤的，模型2)是正確的，這是為什么呢？

（3）判定網絡流模型是否正確的兩個原則：
<1>可行性原則：原題中的每一種可行方案，在建立的網絡流模型中都對應著一個“能求出的”流（一般是滿足一定的條件的流，比如某些邊必須滿流等），注意這里的對應必須是“一一對應”，就是，既不能有可行方案丟失，也不能出現不可行方案；
<2>最優性原則：原題中的最優方案（準確來說是最優方案的結果），在建立的網絡流模型中都對應著一個“能求出的”量（最大流量或者滿足最大流量的前提下的最小費用），也就是，最優結果必須是可以通過這個模型求出的。
一個網絡流模型正確，當且僅當其符合以上兩條原則。
這兩個原則可以檢查所建立的網絡流模型是否正確。比如，對于例2中的兩個模型，模型1)由于最大流對應的是“買的餐巾總數盡可能多”的方案，不是最優方案，因此原題中的最優結果無法求出，顯然不符合最優性原則，因此它是錯誤的。模型2)中，由于可行方案必然能使所有<S, i''>中的邊滿流，且能夠求出，符合可行性原則；最優方案由于<i', T>這條邊的限制，必然是最大流，且是費用最小的最大流，其最小費用為最優結果，符合最優性原則，因此它是正確的。