我正在尝试解决具有额外流量限制的最小成本最大流量问题。似乎经典的网络流算法无法处理这个问题。
这是一个例子：
假设我有一个二分图，左右之间的每条边都有一个成本。与经典的最小成本最大流量问题不同，在我的问题中，每条边的允许流量可以是（0 或 1）或（0 或 2）。如图（示例流程）所示（我没有绘制源和目标）。请注意，对于允许流量为（0 或 2）的边，不允许 flow == 1。
我不希望得到最佳解决方案，但需要在多项式时间内解决它。
我真的很感激任何建议/帮助。
谢谢！
我正在尝试解决具有额外流量限制的最小成本最大流量问题。似乎经典的网络流算法无法处理这个问题。
这是一个例子：
假设我有一个二分图，左右之间的每条边都有一个成本。与经典的最小成本最大流量问题不同，在我的问题中，每条边的允许流量可以是（0 或 1）或（0 或 2）。如图（示例流程）所示（我没有绘制源和目标）。请注意，对于允许流量为（0 或 2）的边，不允许 flow == 1。
我不希望得到最佳解决方案，但需要在多项式时间内解决它。
我真的很感激任何建议/帮助。
谢谢！