Hatena::ブログ(Diary)

競技プログラミング+αなブログ

2012-07-19

蟻本の練習問題埋め2-5(1)

| 03:42

最短路

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

全ての牛のペアに対して繋がりが存在する

解法

牛をノードとし、共演してたらコスト1のエッジを張ったグラフを作る。

グラフが作れたらワーシャルフロイドして全部試すだけ。

しかし、1つの映画に出演する牛の上限がわからないため、グラフの構成に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

解法

与えられた通りの向きで辺を加えたグラフG1と、逆の向きで辺を加えたグラフG2を用意する。

Xを始点としてG1上でダイクストラすると、それぞれの頂点に対して帰りにかかる最小コストが分かる。

Xを始点としてG2上でダイクストラすると、それぞれの頂点に対して行きにかかる最小コストが分かる。

後者は本来の辺を逆に辿るイメージ。

全ての頂点に対して、行きと帰りのコストを調べて最大値を答えとすれば良い。

AOJ 2249 - Road Construction

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2249

問題

頂点数N、辺数Mの無向グラフが与えられる。

辺は距離とコストを持つ。

頂点1から各頂点への距離が変わらないように辺を選ぶ。

そのような辺集合の中で総コストが最小のものを求めよ。

制約

N<=10000, M<=20000

解法

プリム法において、キューの比較関数を累計距離の次にコストが小さい順になるように設定して、全域木を構成すれば良い。

想定解法は最短路DAGを求めて、総コスト最小の最短路木を構成するというもの。

AOJ 2200 - Mr. Rito Post Office

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2200

問題

町がN個あり、陸路または海路が合わせてM個ある。

海路を利用する場合、船を使わなければならず、船は1つしかない。

つまり、海路を利用する場合は、船があるところまで戻らなければならない。

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)で更新する。

前処理として、陸路のみのグラフと海路のみのグラフを作ってワーシャルフロイドしておく。

トラックバック - http://d.hatena.ne.jp/sune2/20120719/1342723320