先考虑流。
\(s->i\)连流量\(d_i\)费用\(0\)
\(i->t\)连流量\(u_i\)费用\(p_i\)
\(i->i+1\)连流量\(\inf\)费用\(c_i\)
\(i+1->i\)连流量\(\inf\)费用\(m_i\)
然而我们并不能通过此题。
考虑从左到右枚举所有和源点连边的边进行增广。
我们需要找到当前边向左/右的最短路。
当前边向右的最短路：由于我们后面的边都没有增广过，所以我们一定不会走反向边。
可以用一个线段树维护代价。如果一个点和汇点连的边代价变为\(0\)，需要把这条边在线段树上删除（赋值为\(\inf\)）
当前边向左的最短路：可能会走反向边。如果一条原边被反向边覆盖，则我们一定会走这条边上的反向边。
考虑用另一个线段树维护权值和我们当前反向边的流量。
每次在线段树上找到最小值的位置。
增广流量：\(\min(最小值位置到t的流量,当前点到最小值位置的流量,s到当前点的流量)\)
分析复杂度：一条边在被向右增广时复杂度显然是\(O(n\log_2n)\)
在被向左增广时，由于我们从左到右增广，所以当前边的流量显然会先增加，后减少。最终只会减到\(0\)一次。
而只有减到\(0\)才会贡献复杂度\(O(\log_2n)\)。
同时，与源点/汇点相邻的边只有减到\(0\)才会贡献复杂度\(O(\log_2n)\)。
所以总时间复杂度\(O(n\log_2n)\)
原文：https://www.cnblogs.com/ctmlpfs/p/14162569.html