我一直在为我的考试准备 DPV 教科书的问题章节做准备。对于其中一个,我遇到了一些麻烦,但我取得了一些进展:
我的解决方案:
我将使用线性规划来最大化 x 其中所有 i 的 SUM {flow_i(s_i, v) 其中 v 是连接到源 s_i} >= x * d_i 的节点
受约束
- 对于每个边 e , f1+..fk <= c_e
- 对于每个边 e,flow_e >= 0
- 还有一些我不确定的限制
我认为我走在正确的轨道上,但我需要一些帮助才能走得更远。我是否应该考虑尝试使用超级节点将其减少为常规的最大流量问题?
任何帮助都会很棒!谢谢你。