有上下界的最小
(
最大
)
流
| INIT: up[][]
为容量上界
; low[][]
为容量下界
;
| CALL: mf = limitflow(n,src,sink); flow[][]
为流量分配
;
|
另附
:
循环流问题
|
描述
:
无源无汇的网络
N,
设
N
是具有基础有向图
D=(V
，
A)
的网络
.
| l
和
c
分别为容量下界和容量上界
.
如果定义在
A
上的函数
| f
满足
: f(v, V) = f(V, v). V
中任意顶点
v,
| l(a)<=f(a)<=c(a),
则称
f
为网络
N
的循环流
.
|
解法
:
添加一个源
s
和汇
t
，对于每个下限容量
l
不为
0
的边
(u, v),
|
将其下限去掉
,
上限改为
c-l,
增加两条边
(u, t), (s, v),
|
容量均为
l.
原网络存在循环流等价于新网络最大流是满流
.
\*==================================================*/
int
up[N][N], low[N][N], flow[N][N];
int
pv[N], que[N], d[N];
void
maxflow(
int
n,
int
src,
int
sink)
{
// BFS
增广
, O(E * maxflow)
int
p, q, t, i, j;
do
{
for
(i = 0; i < n; pv[i++] = 0) ;
pv[t = src] = src + 1; d[t] = inf;
for
(p=q=0; p<=q && !pv[sink]; t=que[p++])
for
(i=0; i
if
(!pv[i]&&up[t][i]&&(j=up[t][i]-flow[t][i])>0)
pv[que[q++]=i]=+t+1, d[i]=d[t]
else if
(!pv[i]&&up[i][t]&&(j=flow[i][t])>0)
pv[que[q++]=i]=-t-1, d[i]=d[t]
}
for
(i=sink; pv[i] && i!=src; ) {
if
(pv[i]>0)flow[pv[i]-1][i]+=d[sink],i=pv[i]-1;
else
flow[i][-pv[i]-1]-=d[sink], i=-pv[i]-1;
}
}
while
(pv[sink]);
}
int
limitflow(
int
n,
int
src,
int
sink)
{
int
i, j, sk, ks;
if
(src == sink)
return
inf;
up[n][n+1] = up[n+1][n] = up[n][n] = up[n+1][n+1] = 0;
for
(i = 0; i < n; i++) {
up[n][i] = up[i][n] = up[n+1][i] = up[i][n+1] = 0;
for
(j = 0; j < n; j++) {
up[i][j] -= low[i][j];
up[n][i] += low[j][i];
up[i][n+1] += low[i][j];
}
}
sk = up[src][sink]; ks = up[sink][src];
up[src][sink] = up[sink][src] = inf;
maxflow(n+2, n, n+1);
for
(i = 0; i < n; i++)
if
(flow[n][i] < up[n][i])
return
-1;
flow[src][sink] = flow[sink][src] = 0;
up[src][sink] = sk; up[sink][src] = ks;
// ! min: src <- sink; max: src -> sink;
maxflow(n, sink, src);
for
(i = 0; i < n; i++)
for
(j = 0; j < n; j++) {
up[i][j] += low[i][j]; flow[i][j] += low[i][j];
}
for
(j = i = 0; i < n; j += flow[src][i++]) ;
return
j;
}