class Graph class Edge attr_accessor :u attr_accessor :v attr_accessor :w def initialize(u, v, w) @u = u @v = v @w = w end end class Vertex attr_accessor :n def initialize(n) @n = n end end end if ARGV[0].nil? or ARGV[1].nil? puts "WRONG!" exit end vertices = [] edges = [] sum = 0 for i in 0..(ARGV[1].to_i - 1) do vertices[i] = Graph::Vertex.new i end fv = 0 File.open(ARGV[0]).each do |line| tv = 0 line.split(",").each do |weight| if weight =~ /[0-9]+/ sum += weight.to_i if tv > fv edges.push(Graph::Edge.new(vertices[fv], vertices[tv], weight.to_i)) end tv += 1 end fv += 1 end edges.sort_by! &:w vnew = [vertices[0]] enew = [] until vnew.sort_by(&:n) === vertices.sort_by(&:n) do edges.each do |e| if vnew.include?(e.u) and !vnew.include?(e.v) vnew.push e.v enew.push e edges.delete e break end end end snew = 0 enew.each do |e| snew += e.w end puts sum - snew