循环流与具有下界的流
$\text{[2020]}\quad \text{Douglas B.West, Introduction to Graph Theroy, Second Edition(图论导引 原书第二版)}$
$\text{chapter 4},\ \textbf{定理4.3.20}$
-
原网络 $G$ 添加从 $t \to s$ 的具有 $+\infty$ 容量的边,此时的网络有个处处守恒的可行流
称为循环流 -
对于可行循环流 $C$,在所有节点处引入供应量 $\sigma (x_i)$ 和需求量 $\partial (x_i)$,给定流量约束
$l(e) \leqslant f(e) \leqslant u(e)$,在每一条边上令 $c(e) = u(e) - l(e)$
$f^{+}(v)$ 表示离开 $v$ 的总流量,$f^{-}(v)$ 表示进入 $v$ 的总流量
$$ \begin{gathered} l^{-}(v) = \sum_{e \in [V(C)-v, v]} l(e) \\\ l^{+}(v) = \sum_{e \in [v, V(C)-v]} l(e) \\\ b(v) = l^{-}(v) - l^{+}(v) \end{gathered} $$
$$ \cdots \xrightarrow{l^{-}(v)} v \xrightarrow{l^{+}(v)} \cdots $$ -
由于可行循环流流量处处守恒,所以 $\sum b(v) = 0$,一个循环可行流在每个顶点满足
$f^{+}(v) - f^{-}(v) = 0$,令 $f’(e) = f(e) - l(e)$
$$ \begin{cases} f’^{+}(v) = f^{+}(v) - l^{+}(v) \\\ f’^{-}(v) = f^{-}(v) - l^{-}(v) \end{cases} $$
可以推出
$$ \begin{cases} l’^{-}(v) = f^{-}(v) - f’^{-}(v) \\\ l’^{+}(v) = f^{+}(v) - f’^{+}(v) \end{cases} \xrightarrow{f^{+}(v) = f^{-}(v)} $$
所以有
$$ l^{-}(v) - l^{+}(v) = b(v) = f’^{+}(v) - f’^{-}(v) $$
也就是说,$f$ 是 $C$ 中的一个可行流当且仅当
$f’$ 满足流量约束 $0 \leqslant f’(e) \leqslant c(e)$
并且在每个顶点处满足 $f’^{+}(v) - f’^{-}(v) = b(v)$ -
这样可以将循环流问题转换为一个供应量和需求量的问题,为了满足流量守恒,需要这样做
-
$b(v) \geqslant 0$,那么 $v$ 向网络供应流量 $|b(v)|$
建立一个超级源点 $S$,令容量 $c(S, v) = |b(v)|$ -
$b(v) < 0$,则 $v$ 对网络有 $|b(v)|$ 的需求量
建立一个超级汇点 $T$,$c(v, T) = |b(v)|$ -
这样我们构造出了新网络 $G$,并且之前已经证明了
$C$ 有一个可行循环流 $f$ 当且仅当 $G$ 有一个满流浸润了离开 $S$ 或进入 $T$ 的所有边
此时我们称 $G$ 保持一个浸润状态
$\textbf{algorithm}$
-
根据上述方法在原网络 $G$ 的基础上,建立超级源点 $S$ 和 超级汇点 $T$,来满足供需关系
-
在原网络 $G$ 的汇点 $t$ 和 源点 $s$ 中,连一条边使得 $c(t, s) = +\infty$
此时构造出可行循环流网络,新网络记为 $N$ -
$\textbf{dinic}(N)$ 判断新网络是否浸润
-
如果浸润,在浸润状态下 $N$ 的一个可行流记为 $f_0$
那么 $f_0$ 中从 $s \to t$ 的流量 $f_0(s \to t) = e(t \to s)$
$e(t \to s)$ 表示执行完 $\textbf{dinic}$ 之后,边 $(t, s)$ 的容量 -
去掉循环流的边 $(t, s)$,再次执行 $\textbf{dinic}$ 算法,使得 $s \to t$ 没有增广路
$f’ = \textbf{dinic}(s, t)$,表示执行增广能够增加的流量为 $f’$
则此时 $(f_0 \uparrow f’) = f$,$f$ 即为 $s \to t$ 的上下界最大流
下面来证明这个算法的正确性
注意,这里对于浸润流 $f_0$,$f_0(s \to t)$ 的流量是分散的(因为 $s \to t$ 的路径上可能有很多点)
而 $f_0(t \to s)$ 是可以直接求的,因为我们在残量网络上连了一条 $t \to s, \ c(t, s) = +\infty$ 的边
因为 $f_0(s \to t) = f_0(t \to s) = c(s, t)$,所以求出 $f_0$ 之后
只需要在残量网络中找到表示 $\textbf{edge}(s, t)$ 这条边,即表示 $f_0(s \to t)$
const int maxn = 210, maxm = (10000 + maxn) * 2;
const int inf = 0x3f3f3f3f;
int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1, tot = 0;
int A[maxn];
int n, m, s, t, S, T;
void add(int a, int b, int c) {
ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
ver[++idx] = a; e[idx] = 0; ne[idx] = head[b]; head[b] = idx;
}
int d[maxn], cur[maxn];
bool bfs() {
memset(d, -1, sizeof d);
queue<int> q;
d[S] = 0, cur[S] = head[S];
q.push(S);
while (q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (d[y] == -1 && e[i]) {
d[y] = d[x] + 1;
cur[y] = head[y];
if (y == T) return true;
q.push(y);
}
}
}
return false;
}
int dinic(int u, int lim) {
if (u == T) return lim;
int flow = 0;
for (int i = cur[u]; i && lim > flow; i = ne[i]) {
cur[u] = i;
int v = ver[i];
if (d[v] == d[u] + 1 && e[i]) {
int t = dinic(v, min(e[i], lim - flow));
if (!t) d[v] = -1;
flow += t, e[i] -= t, e[i^1] += t;
}
}
return flow;
}
int dinic() {
int res = 0, flow;
while (bfs()) while (flow = dinic(S, inf)) res += flow;
return res;
}
int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d%d%d", &n, &m, &s, &t);
S = 0, T = n+1;
for (int i = 0; i < m; i++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b, d-c);
A[a] -= c, A[b] += c;
}
for (int i = 1; i <= n; i++) {
if (A[i] > 0) tot += A[i], add(S, i, A[i]);
else if(A[i] < 0) add(i, T, -A[i]);
}
add(t, s, inf);
// then solve
if (dinic() != tot) {
puts("No Solution");
return 0;
}
int res = e[idx];
e[idx] = e[idx-1] = 0;
S = s, T = t;
int ans = res + dinic();
printf("%d\n", ans);
}
请问第一次的res 为什么不用加入减去的底流呢