107問目
「最小全域木」を求める問題、だそうです。グラフ問題に疎い自分は超俺流アルゴリズムで実装したため、UPする気にならず、放ったらかしてました。
jeneshiccさんの方法が簡単そうなのだけど、fglパッケージを入れていないので、まずは自分で書くことに。
どうやら最小全域木を求めるにはPrim法とKruskal法があるらしい。Kruskal法で解くにはDisjointSetsを実装しなければならず、けっこう面倒くさい。という訳で、Prim法です。
import Data.List main = print . euler107 . weights =<< readFile "network.txt" weights :: String -> [[Int]] weights = map (read . ("[" ++) . (++ "]")) . lines . map replace where replace '-' = '0' replace c = c euler107 :: [[Int]] -> Int euler107 ws = div (sum (map sum ws)) 2 - prim ws [0] [1..length ws - 1] 0 prim :: [[Int]] -> [Int] -> [Int] -> Int -> Int prim _ _ [] n = n prim ws as bs w = prim ws (b':as) (delete b' bs) (w+w') where (w',(a',b')) = minimum [ (w,(a,b)) | a <- as, b <- bs, let w = ws!!a!!b, w /= 0 ]