Life Goes On

まあまあだけど楽しんでる方です

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 ]