蟻本の練習問題埋め2-5(1)
最短路
AOJ 0189 - Convenient Location
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0189
ワーシャルフロイドして全部の町を試す。
PKU 2139 - Six Degrees of Cowvin Bacon
http://poj.org/problem?id=2139
問題
N匹の牛が映画に出演する。
M個の映画について、どの牛が出演したかの情報が与えられる。
ある牛について、その牛以外の牛とのベーコン指数（っぽいもの）の平均を求める。
この平均の最小値を求めよ。
出力するのは、平均を100倍し整数で表したもの
制約
N<=300
M<=10000
全ての牛のペアに対して繋がりが存在する
解法
牛をノードとし、共演してたらコスト１のエッジを張ったグラフを作る。
グラフが作れたらワーシャルフロイドして全部試すだけ。
しかし、１つの映画に出演する牛の上限がわからないため、グラフの構成にO(N^2M)かかってしまう。
このオーダーを落とす方法はあるのだろうか…
あと出力を整数に丸める方式が書いてなかったが、切り捨てっぽい。
スッキリしない問題。
POJ 3259 - Wormholes
http://poj.org/problem?id=3259
負閉路検出するだけ
M個の辺は両方向で、W個の辺は片方向であることに注意
POJ 3268 - Silver Cow Party
http://poj.org/problem?id=3268
問題
ノード数N,辺数Mの有向グラフがある。
ある頂点から頂点Xまで行き、頂点Xからもとの頂点まで戻るときの最小コストの最大値を求めよ。
制約
N<=1000
M<=100000
AOJ 2249 - Road Construction
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2249
問題
頂点数N、辺数Mの無向グラフが与えられる。
辺は距離とコストを持つ。
頂点１から各頂点への距離が変わらないように辺を選ぶ。
そのような辺集合の中で総コストが最小のものを求めよ。
制約
N<=10000, M<=20000
解法
プリム法において、キューの比較関数を累計距離の次にコストが小さい順になるように設定して、全域木を構成すれば良い。
想定解法は最短路DAGを求めて、総コスト最小の最短路木を構成するというもの。
AOJ 2200 - Mr. Rito Post Office
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2200
問題
町がN個あり、陸路または海路が合わせてM個ある。
海路を利用する場合、船を使わなければならず、船は１つしかない。
つまり、海路を利用する場合は、船があるところまで戻らなければならない。
R個の町を巡る順番z[i]が与えられるので、このときの最小移動距離を求めよ。
ただし、最初は町z[1]にいて船もそこにある。
制約
N<=200
M<=10000
R<=1000
解法
z[i]からz[i+1]に移動するとき、
- 陸路のみ
- 陸路 → 海路 → 陸路
のうち、どちらかのタイプの経路を辿る。
海路 → 陸路 → 海路
などは、船を降りた町まで戻ることを考えると、陸路の部分が要らなくなるので無駄。
これを念頭に踏まえ、
dp[i][j] = z[i]まで移動したとき、船が町jにあるときの最小累計移動距離
としてDPする。
dp[i][j] = min{dp[i-1][k]+(船をkからjまで移動して、z[i-1]からz[i]に達するときの最小移動距離)}
によりO(N)で更新する。
前処理として、陸路のみのグラフと海路のみのグラフを作ってワーシャルフロイドしておく。
