流网络技术咨询：非零边0值s-t流与最小瓶颈边集求解

问题1：判断是否存在含至少一条正流量边的0值s-t有效流 #

核心思路 #

0值s-t流意味着s和t的净流量为0，但可以存在内部环流（流量在某个有向环中循环，不影响s-t的净流量）。问题等价于：原网络中是否存在一个所有边容量均大于0的有向环——只要存在这样的环，就能给环上每条边分配正流量，形成满足要求的有效流；反之，若不存在这样的环，所有0值s-t流只能是全0流。

高效算法 #

1. 预处理子图：从原网络G中移除所有容量为0的边，得到子图G'。
2. 检测有向环：对G'进行拓扑排序。若拓扑排序无法完成（即G'存在环），则存在满足要求的流；若G'是无环有向图（DAG），则不存在。

时间复杂度：O(V+E)，拓扑排序的线性时间复杂度足以处理大规模网络。

问题2：找出扩容可提升最大流的瓶颈边集 #

核心思路 #

根据最大流最小割定理，扩容某条边能提升最大流的充要条件是：

1. 该边已被当前最大流饱和（即f(e) = c(e)，否则扩容无法增加现有流量的利用）；
2. 该边属于所有最小s-t割（若存在某个最小割不包含该边，扩容后这个割的容量仍为原最小割容量，最大流不会变化）。

通过残余网络的强连通分量（SCC）可高效判断边是否属于所有最小割：

• 残余网络中，同一个SCC内的节点可互相到达，因此最小割不会将同一SCC内的节点分开；
• 若饱和边e=(u,v)的两个端点不在同一SCC中，且u在s的可达范围内、v在t的可达范围内，则该边属于所有最小割。

高效算法 #

1. 构建残余网络：基于给定的最大流f，构建残余网络（正向边残余容量为c(e)-f(e)，反向边残余容量为f(e)）。
2. 计算强连通分量：用Tarjan或Kosaraju算法求出残余网络中所有节点的SCC，时间复杂度O(V+E)。
3. 确定可达范围：
   • 从s出发在残余网络中BFS/DFS，得到s可达的节点集合S_reach；
   • 从t出发在残余网络的反向图中BFS/DFS（等价于找残余网络中能到达t的节点），得到集合T_reach。
4. 筛选瓶颈边：遍历所有边e=(u,v)：
   • 若f(e) < c(e)：跳过（不饱和，扩容无效）；
   • 若u ∈ S_reach且v ∈ T_reach且scc(u) != scc(v)：将e加入瓶颈边集。

时间复杂度：O(V+E)，全程线性时间，无需枚举所有最小割，避免了指数级计算量。

内容的提问来源于stack exchange，提问作者Nadav Avnon