プログラミングコンテストチャレンジブック 3-6 その4
3-6 ネットワークフローの続きです。
- 最小費用流
- 最小コスト通信 - 通信費用が辺毎に決まっている時に費用を最小にする(転送量は決まってる)
- 最短路を求めつつ貪欲法で解く
- フロー f が最小費用 <=> 残余グラフに負の閉路が存在しない
- 最短路を求めるためにダイクストラ法を利用するため、ノードにポテンシャルを持たせて辺の重みを正の数にする手法
- 最小コスト通信 - 通信費用が辺毎に決まっている時に費用を最小にする(転送量は決まってる)
- 練習問題
- Asteroids - NxN の格子にK個の小惑星を縦横のビーム(一直線状の全ての小惑星を破壊できる)で最小の回数で破壊する
- ビームの打ちかた(縦横、位置)をノードとして、それで破壊される小惑星を辺にすると、二部グラフになる→最大マッチングに帰着
- この問題文から二部グラフマッチングを見抜くのはすごい
- Evacuation - XxY マスの部屋で火事から脱出
- これもドアと人をノードとして二部グラフマッチングに帰着する。そんな発想できない!
- Dining - 牛に食べ物と飲み物を数種類ずつ用意した時に好みの食べ物と飲み物にありつける牛を最大にする
- これは比較的簡単に二部グラフマッチングが2つ合体した問題だとわかります
- まず食べ物、飲み物のそれぞれについて独立してマッチンググラフを作成
- 次にこの2つのグラフの同じ牛を表すノードを連結して、最大流量問題に帰着(容量はすべて1)
- Dual Core CPU - デュアルコアのCPUで実行するモジュール毎にコアによってコストが違う場合のスケジューリング
- モジュールをノードとして、s, t をコアの種類として s-t カットがコスト。最小カットを求めればよい
- モジュール間のデータ交換コストはモジュール間を繋ぐ双方向の辺にする
- Farm Tour - 家から畑を通って納屋まで行って、逆向きに返ってくる。ただし同じ道は通らないとした時の最短路
- 往復でかつ往路で使った辺を通らないので単純に最短路を探してもだめ
- 流量2 の最小費用流問題に帰着
- Evacuation Plan - 今度はビルと核シェルターの問題
- 重みつきの二部グラフマッチング → 最小費用流として解ける
- The Windy's - おもちゃと工場の割り当て問題
- おもちゃの完成時間まで(待ち時間も含めて)の平均になっているのがみそ。問題文が難しい
- 最小費用流に帰着
- Intervals - いくつかの重みをもつ区間から重なり最大数の制限の元で同時に選択できる区間の重みの和を最大化
- Asteroids - NxN の格子にK個の小惑星を縦横のビーム(一直線状の全ての小惑星を破壊できる)で最小の回数で破壊する
これで 3-6 ネットワークフローの節は終了です。練習問題をみると、まず問題文からそれがグラフやフローの問題だと気がつくのが難しいものが多いのがよくわかります。解法やその実装方法を熟知するのももちろんですがこの発想の転換が一番難しそうですね。
