我正在寻找最小多切算法的实现。我的问题类似于此处定义的问题，我引用：
最小多切。输入包含一个加权的无向图 G = (V,E)，对于 E 中的每条边具有非负权重 c_k，以及一组终端对 {(s1,t1);(s2,t2)... (sk,tk)}。多割是一组边，其删除会断开每个终端对。
不同之处在于我正在考虑有向图。我知道这个问题是 NP 难的，但是为了获得更有效的算法，可以进行一些近似。但是，我找不到任何实现，甚至找不到明确的伪算法。
任何帮助都感激不尽！
问问题
17 次