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

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

### 基本建图

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

$$u$$至少流出$$l$$的流量,$$v$$至少流入$$l$$的流量,所以建边$$(S,v)=l,(u,T)=l$$;

### 最大流

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

$$s->t$$跑的是$$S->T$$的反向边,这时下界的流量已经在反向边中了,$$(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

### 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

### 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