[学习笔记]有上下界的网络流([learning notes] network flow with upper and lower bounds)

对于有上下界的网络流问题,涉及判是否有解及求解最大/小流,费用流.

基本建图

建立超级源\(S\),超级汇\(T\).
对于边\((u,v)\)=\([l,u]\),将其拆成三条边:

  • \((S,v)=l\);
  • \((u,v)=u-l\);
  • \((u,T)=l.\)

因为对于边\((u,v)=[l,u]\),
\(u\)至少流出\(l\)的流量,\(v\)至少流入\(l\)的流量,所以建边\((S,v)=l,(u,T)=l\);
而\(u->v\)有\(u-l\)的流量是自由流,所以建边\((u,v)=u-l\).

显然\(S->u,u->T\)有可能有多条边,合并这些边,节省空间.

无源汇

可行流

求\(S->T\)的最大流,从\(S\)出发的边全部满流则可行,因为说明所有边的下界均已满足.每条边的实际流为自由流+流量下界.

有源汇

可行流

加一条边\((t,s)=+\infty\).转成无源汇.
求\(S->T\)的最大流,从\(S\)出发的边全部满流则可行.

最大流

求出可行流后,在残量网络上求\(s->t\)的最大流.

理由:
\(s->t\)跑的是\(S->T\)的反向边,这时下界的流量已经在反向边中了,\((t,s)=+\infty,S,T\)不会影响到最大流,所以是合法的答案.

理由:
\(s->t\)跑的是\(S->T\)的反向边,这时下界的流量已经在反向边中了,\((t,s)=+\infty,S,T\)不会影响到最大流,所以是合法的答案.

最小流

先不加\((t,s)=+\infty\)这条边,这时跑\(S->T\)的最大流可求出\(t->s\)的最大流,也就是在合法的情况下最多能减去多少.
然后再加\((t,s)=+\infty\)这条边,此时残量网络\(S->T\)的最大流即为答案.

2017-03-14 11:20:47

2017-03-14 11:20:47

————————

For the network flow problem with upper and lower bounds, it involves judging whether there is a solution and solving the maximum / small flow and cost flow

Basic construction drawing

Create super source \ (s \), super sink \ (t \)
For edge \ ((U, V) \) = \ ([l, u] \), split it into three edges:

  • \((S,v)=l\);
  • \((u,v)=u-l\);
  • \((u,T)=l.\)

Because for edge \ ((U, V) = [l, u] \),
\(U \) at least flows out of \ (L \) and \ (V \) at least flows into \ (L \), so build an edge \ ((s, V) = L, (U, t) = l \);
The flow with \ (U – & gt; V \) and \ (u-l \) is free flow, so the edge is built \ ((U, V) = u-l \)

Obviously \ (s – & gt; u, u – & gt; t \) may have multiple edges. Merge these edges to save space

Passive sink

Feasible flow

Find the maximum flow of \ (s – & gt; t \), and it is feasible if all the edges starting from \ (s \) are full, because it means that the lower bounds of all edges have been met. The actual flow of each edge is free flow + lower bound of flow

Source and sink

Feasible flow

Add an edge \ ((T, s) = + \ infty \). Convert to passive sink
Find the maximum flow of \ (s – & gt; t \), and it is feasible if all the edges starting from \ (s \) are full

Maximum flow

After finding the feasible flow, find the maximum flow of \ (s – & gt; t \) on the residue network

reason:
\(s – & gt; t \) runs the reverse side of \ (s – & gt; t \), and the flow of the lower bound is already in the reverse side. \ ((T, s) = + \ infty, s, t \) will not affect the maximum flow, so it is a legal answer

reason:
\(s – & gt; t \) runs the reverse side of \ (s – & gt; t \), and the flow of the lower bound is already in the reverse side. \ ((T, s) = + \ infty, s, t \) will not affect the maximum flow, so it is a legal answer

Minimum flow

Without adding the edge \ ((T, s) = + \ infty \), the maximum flow of running \ (s – & gt; t \) can be calculated, that is, the maximum flow of \ (T – & gt; s \) can be subtracted under legal conditions
Then add the edge \ ((T, s) = + \ infty \), and the maximum flow of residual network \ (s – & gt; t \) is the answer

2017-03-14 11:20:47

2017-03-14 11:20:47