P4843题解
建模
一到比较裸的有源汇上下界最小流。每条边必走一次，要求求出最小的流量。由于比较裸，这里当作上下界流的例题讲。
什么是有源汇上下界最小流
顾名思义，就是在最大流的基础上增加了边的最小经过流量，使得整个网络可行，并且找出最小流量的方案。一个比较朴实的想法就是将一个边的最大限制减去最小限制，跑最大流即可。但是该方法并不满足流量守恒定律，因此做出一下调整。
我们在图中新建两个虚拟点，设置为新的虚拟源汇点。设 \(d_u\) 为点 \(u\) 所以入度边中的流量下限与所有出度中的流量下限之差。
标签：题解,最小,流量,下界,P4843,汇上 From： https://www.cnblogs.com/mjsdnz/p/17571423.html