手绘风网站,一般拍卖会在什么网站做,个人网站建设的小清新图片,网站流量查询无源汇有上下界可行流
法一#xff08;据说适合点少边多的图#xff09;#xff1a;
建图方法
首先建立附加源点ss和附加汇点tt对于原图中的边x-y#xff0c;若限制为[b,c]#xff0c;那么连边x-y#xff0c;流量为c-b对于原图中的某一个点i#xff0c;记d(i…无源汇有上下界可行流
法一据说适合点少边多的图
建图方法
首先建立附加源点ss和附加汇点tt对于原图中的边x-y若限制为[b,c]那么连边x-y流量为c-b对于原图中的某一个点i记d(i)为流入这个点的所有边的下界和减去流出这个点的所有边的下界和
若d(i)0那么连边ss-i流量为d(i)若d(i)0那么连边i-tt流量为-d(i)
求解方法
在新图上跑ss到tt的最大流若新图满流那么一定存在一种可行流此时原图中每一条边的流量应为新图中对应的边的流量这条边的流量下界
法二据说适合点多边少的图
建图方法
首先建立一个源点ss和一个汇点tt一般称为附加源和附加汇。对于图中的每条弧u,v假设它容量上界为c下界b那么把这条边拆为三条只有上界的弧。
一条为ss,v容量为b一条为u,tt容量为b一条为u,v容量为c−b。
其中前两条弧一般称为附加弧。
求解方法
以ss为源点以tt为汇点对这张图跑最大流。如果所有的附加弧都满流则原图有可行流。这时每条非附加弧的流量加上它的容量下界就是原图中这条弧应该有的流量。
理解方法
对于原图中的每条弧我们把c−b称为它的自由流量意思就是只要它流满了下界这些流多少都没问题。
既然如此对于每条弧u,v我们强制给v提供b单位的流量并且强制从u那里拿走b单位的流量这一步对应着两条附加弧。
如果这一系列强制操作能完成的话也就是有一组可行流了。
注意这张图的最大流只是对应着原图的一组可行流而不是原图的最大或最小流。
有源汇有上下界可行流
建图方法
在原图中添加一条边t-s流量为inf其余建图方法与无源汇有上下界可行流相同
求解方法
同无源汇有上下界可行流弧t,s的流量就是原图的总流量
理解方法
有源汇相比无源汇的不同就在于源和汇是不满足流量平衡的那么连接t,s之后源和汇也满足了流量平衡就可以直接按照无源汇的方式建模。
注意这张图的最大流只是对应着原图的一组可行流而不是原图的最大或最小流。
有源汇有上下界最大流
建图方法
同有源汇有上下界可行流
求解方法
在新图上跑ss到tt的最大流若新图满流那么一定存在一种可行流记此时∑f(s,i)sum1 即此时t-s的最大流也就是求反向边s-t的流量将t-s这条边拆掉在新图上跑s到t的最大流记此时∑f(s,i)sum2 即maxflowst最终答案即为sum1sum2
理解方法
为什么要在已经有了流量的图上跑最大流因为那张图保证了每条弧的容量下界在这张图上跑最大流实际上就是在容量下界全部满足的前提下尽量多得获得“自由流量”。
有源汇有上下界最小流
建图方法常用的一种
按照有源汇可行流的方法建图但是不要建立t,s这条弧。
求解方法
求ss-tt最大流连边t-s,inf求ss-tt最大流若满流则存在可行流答案即为边t-s,inf的实际流量
理解方法
在跑完有源汇可行流之后弧t,s的流量就是原图的流量。
第一遍做的时候并无t-s这条边所以s-t的流量已经尽力往其它边流了。
加上t-s这条边后流过这条边的都是些剩余的流不到其他边的流量从而达到尽可能减少t-s这条边上的流量的效果即减小了最终答案。
注意最小流判断是否有可行解的位置与时机与另外几种上下界网络流的不同
有源汇有上下界费用流
法一据说适合点少边多的图
建图方法
首先建立附加源点ss和附加汇点tt对原图中某边x-y若限制为[b,c]费用为cost那么连边x-y流量为c-b费用为cost对原图中某点i记d(i)为流入这个点的所有边的下界和减去流出这个点的所有边的下界和
若d(i)0那么连边ss-i流量为d(i)费用为0若d(i)0那么连边i-tt流量为-d(i)费用为0
连边t-s流量为inf费用为0
求解方法
跑ss-tt的最小费用最大流答案即为求出的费用原图中边的下界*边的费用
法二据说适合点多边少的图
建图方法
首先建立附加源ss和附加汇tt。对于图中的每条弧u,v假设它容量上界为c下界b费用为cost那么把这条边拆为三条只有上界的弧。
一条为ss,v容量为b费用为0一条为u,tt容量为b费用为0一条为u,v容量为c−b费用为cost。
求解方法
跑从ss到tt的费用流答案即为求出的费用原图中边的下界*边的费用
