PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 107 / 最短ネットワーク

問題の概要

頂点数40の重みつき有向グラフgが与えられる。その最小全域木をg'とする。gの重みの総和とg'の重みの総和の差を求めよ。

本家:Problem 107 - Project Euler
日本語訳:Problem 107 - PukiWiki

解法

頂点数7のとき

WeightedAdjacencyGraph でグラフを作り,FindSpanningTree で最小全域木を求めます。問題文中で与えられているサンプルでやってみましょう。

まずはグラフ作成。

f:id:variee:20180531161218p:plain

最小全域木は赤い点線のようになります。

f:id:variee:20180531161428p:plain

頂点数40のとき

同じ要領で頂点数40の場合を処理し,重みの総和の差を計算します。

約3秒かかっていますが,これはデータファイルをダウンロードしているためです。ローカルでやると0.004秒ほどで答えが出ます。

どんなグラフになるか

実際にどんな最小全域木ができるのか見てみましょう。

f:id:variee:20180531162455p:plain

元のグラフと重ねるとこうなります。

f:id:variee:20180531162510p:plain