才疏学浅，理论知识不够。请教大家一个问题。图里面的最大流问题，求的是两点之间的，那么有没有办法求出来所有节点的能够通过的？直接依次求，更新权重就可以了嘛？

[microxiaoxiao]

[GuuJiang]

@microxiaoxiao 重新准确描述下，你的意思是，是否存在一个算法一次性求出指定源点到其他所有汇点的最大流?还是说一次性求出所有点两两之间的最大流?(类似于最短路问题中的 floyd 算法那样)

[microxiaoxiao]

@GuuJiang 求所有的。就是这个集群最大能接受多少流

[MoYi123]

@microxiaoxiao 那到底是第一种情况还是第二种呢?
第一种情况设置一个虚拟终点, 除了起点外的点到虚拟终点的权重都是无限大, 用起点到虚拟终点跑一次最大流即可
第二种不会.

[GuuJiang]

@microxiaoxiao 你可能对最大流的定义有点误解，当我们在讨论一个最大流时是不能脱离源点汇点单独存在的，换句话说只有预先指定了源点和汇点，接下来才能讨论最大流
不过我也大概理解了你的意思，你的意思应该是“在可以任意选择源点和汇点的前提下，所有任意组合的最大流中的最大值”，这个确实没有认真想过，和这个比较接近的是有多个源和多个汇的问题，解决方法是添加一个超级源和超级汇，然后求解，但是我猜这个方法应该是无法直接套用到你说的这个场景的，可能需要一些手段来规避同一个结点既作为源又作为汇的情况，否则的话求出来直接就是无穷大了，细节容我再想想

[GuuJiang]

刚才搜索了下，对于这个问题，目前没有什么比针对每一对结点分别跑一遍最大流算法更优的算法

[vance123]

最大流问题也是线性规划问题，要不试试万能的求解器？

[nagatoism]

最小割问题
https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm

[nagatoism]

全局的最小的 最大流等于全局的最小割。

[microxiaoxiao]

@GuuJiang 哈哈，要不怎么说才疏学浅呢，就是我不太了解，其实问题更抽象一点，就是现在有多个节点，找到这样的组合，使得能够规划出来的两两节点值加起来最大。那么这个就是整个集群对外提供的输入输出能力