Travelling tours (1077) †

概要 †

N 個の都市が M 本の双方向移動が可能な道路でつながっている．いま，3 以上の都市を巡回するようなツアーを複数企画する．このとき，次の条件を満たすような T 種類のツアーを企画せよ．

• それぞれのツアーに対して，別のツアーでは通行しない道路が少なくとも 1 本は存在する．
• T は最大値．

解法 †

都市を頂点，道路を辺とみなし，全体をグラフとして考える．

グラフ G が連結ならば，全域木 T を 1 つとり，T に属さない各辺 e に対して，e と T でできる閉路（常にちょうど 1 個存在）をすべて列挙すればよい．一般のグラフに対しては連結成分ごとに考える．

上記のようにすれば閉路の数が最大になる（らしい）．

ソース †

準備中