試験準備のために、DPV テキストの質問の章に取り組んでいます。そのうちの 1 つについて、私はいくつかの問題を抱えていますが、いくつかの進歩を遂げました。
私の解決策：
線形計画法を使用して x を最大化します。ここで、SUM {flow_i(s_i, v) for all i where v is nodes connected to source s_i} >= x * d_i
制約を受ける
- 各エッジ e に対して、f1+..fk <= c_e
- 各エッジ e について、flow_e >= 0
- そして、私が確信していないいくつかの制約
私は正しい軌道に乗っていると思いますが、もう少し先に進むための助けが必要です。スーパーノードを使用して、これを通常の最大フローの問題に減らすことを検討する必要がありますか?
どんな助けでも素晴らしいでしょう！ありがとうございました。