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>这条边的限制，必然是最大流，且是费用最小的最大流，其最小费用为最优结果，符合最优性原则，因此它是正确的。