プログラミングコンテストチャレンジブック 3-6 その1

第3章 3-6 「水を流して問題を解く "ネットワークフロー"」からです。この節は長いので数日に渡って読むことになりそうです。

• 最大流
  • 最大通信量
    • グラフの問題なんだけど特定の経路のコストを注目するのではなくて全体で(可能な全ての経路を利用して)どのくらいの流量が確保できるかという問題
    • 貪欲法に、一度決めた辺の流量を「押し戻す」ことを許可した手法で求められる(Ford-Fulkerson 法)
• 最小カット
  • グラフの「カット」とはグラフのある部分節集合から出ていく辺の集合
  • カットの容量とはカットの容量の総和
  • s-t のフロー <= 任意の s-t カットの容量(カットは逆向きの辺の容量を加味しないので)
  • 故に最小の s-t カット容量が s-t フローの最大流量
• コラムより。 source とsink(目的ノード、t) が複数あった時 は 各 si と ti の間の最大流量を計算する。ただし si, ti 毎に目的地が対応している場合は多品種フローと呼ばれ、効率的な解法が知られていない
• コラムより。ノードに容量制限がある場合は、ノードを入口と出口の2つのノードに分けて考えて、それらの間を繋ぐ辺に容量制限を持たせれば一般的な問題に帰着できる
• Dinic 法というより高速な方法もある