解説と若干違っていたので

概要

鉄道会社の乗り換えを最小化せよ

かなり雑なブログ記事です

Hypergraph

ハイパーグラフとは，ハイパー辺と頂点から構成されるグラフのようなもの．通常の辺は2つの頂点に接続するが，ハイパー辺は1つ以上の頂点に接続する．

ある鉄道会社の路線が連結でないとき，それぞれの連結成分は異なる鉄道会社である，と解釈しても答えは変わらない．

よって，ある鉄道会社の路線が連結でないときは，別の鉄道会社として新たに番号を割り当てる．（適当に実装すると最悪時間O(M²)になるっぽいので要考察）

それぞれの鉄道会社の辺集合を，ハイパー辺に置き換える．具体的には，鉄道会社の辺集合が接続する頂点を全て列挙して，列挙した頂点に接続するハイパー辺に置き換える．

辺コスト1の，ハイパーグラフ上の最短経路問題になる．

辺コスト1の，ハイパーグラフ上の最短経路問題を解くために，ハイパーじゃないグラフに構築し直して，最短経路問題を解く．

グラフ→ハイパーグラフ→グラフの変換ですね．

ハイパー辺をスターに置き換える．つまり，ハイパー辺ごとに頂点を作成して，ハイパー辺が接続する頂点と作成した頂点を接続させる．

このグラフに対して最短経路問題を解くと，辺コスト2のハイパーグラフ上の最短経路のコストが得られる．2で割って出力．

僕はこんな感じ．各鉄道会社について，次の処理を行う．

普通Unionfindはvectorで実装されていて，初期化にO(N)かかってしまうので，mapで実装し直す．時間計算量はO(Nlog^c N)ぐらい．cは2から4ぐらい．

最初はdfsだったんですが，落ちた．撃墜ケースも分からず．