Submission #2384155

---

Source Code Expand

require 'pp'
# IS_DEBUG = true
IS_DEBUG = false
def dputs str
	if(IS_DEBUG)
		puts str
	end
end
def dpp str
	if(IS_DEBUG)
		pp str
	end
end

require 'pp'

def one2zero(g)
	g.map{|v1,v2,w| [v1-1,v2-1,w]}
end

w_i = 2

# answer the weight of min spanning tree of g containing e
# g is all edges of the graph, representating the graph
def kraskal(g_sorted, num_vertexes, e=[])
	def connect(v1,v2,v2t)
		# t2 merge to t1
		t1 = v2t[v1]
		t2 = v2t[v2]
		v2t.map!{|t| t == t2 ? t1 : t}
	end
	
	# init
	# generate forest mapping vertex i to tree i
	# 0 indexed : vertex i+1 (1 indexed) and tree i+1 map to vartex[i]=i
	v2t = Array.new(num_vertexes){|i| i}
	num_rest = num_vertexes - 1
	w_tree = 0
	
	# optinal behavior
	# fixed edge to select
	e.each{|v1,v2,w|
		num_rest -= 1
		w_tree += w
		connect(v1,v2,v2t)
	}

	# start
	g_sorted.each{|v1,v2,w|
		if(num_rest == 0)
			break
		end
		dputs "compare tree of #{v1} #{v2} #{w} : #{v2t[v1]} #{v2t[v2]}"
		if(v2t[v1]!=v2t[v2])
			connect(v1,v2,v2t)
			num_rest -= 1
			w_tree += w
		end
	}
	return w_tree
end

def mod_pow(a,n)
	mod = 1000000007
	if(n==1)
		return a
	end
	m = n/2
	mpa = mod_pow(a,m)
	mpa2 = (mpa * mpa) % mod
	if(n%2 != 0)
		 mpa2 = (mpa2 * a) % mod
	end
	mpa2
end
def f(x,d_min,num_edge)
	num = d_min.inject(0){|sum,n| n <= x ? sum+1 : sum}
	dputs "num is #{num}"
	if(num == 0)
		mod_pow(2, num_edge)
	else
		mod_pow(2,num_edge-num+1)
	end
end

N,M=gets.chomp.split(' ').map{|n| n.to_i}
X,d=gets.chomp.split(' ').map{|n| n.to_i}
g = Array.new(M)
0.upto(M-1){|d|
	g[d]=gets.chomp.split(' ').map{|n| n.to_i}
}
g = one2zero(g)
g = g.sort{|e1,e2| e1[w_i] <=> e2[w_i]}

d_min = Array.new(M)
g.each_with_index{|e,i|
	d_min[i] = kraskal(g,N,[e])
}
dputs "dmin is "
dpp d_min

puts "#{f(X-1,d_min,M) - f(X,d_min,M)}"

Submission Info

Compile Error

./Main.rb:89: warning: shadowing outer local variable - d
./Main.rb:87: warning: assigned but unused variable - d

Judge Result