build_residual_network

build_residual_network(G, capacity)

构建一个残差网络并初始化零流。

来自输入图 G 的残差网络 R 与 G 拥有相同的节点。R 是一个有向图（DiGraph），当且仅当 (u, v) 不是自环且 G 中存在边 (u, v) 或边 (v, u) 时，R 中包含一对边 (u, v) 和 (v, u)。

对于 R 中的每条边 (u, v)，如果该边存在于 G 中，则 R[u][v]['capacity'] 等于其在 G 中的容量；否则为零。如果容量是无限的，R[u][v]['capacity'] 将是一个很高的任意有限值，不会影响问题的解。该值存储在 R.graph['inf'] 中。对于 R 中的每条边 (u, v)，R[u][v]['flow'] 表示边 (u, v) 的流函数，并满足 R[u][v]['flow'] == -R[v][u]['flow']。

流值定义为流入汇点 t 的总流量，存储在 R.graph['flow_value'] 中。如果未指定 cutoff，则仅使用满足 R[u][v]['flow'] < R[u][v]['capacity'] 的边 (u, v) 到达 t 的可达性，将导出一个最小 s-t 割。