Submission #1292459

---

Source Code Expand

require 'set'

A, T, K = gets.split.map(&:to_i)
areas, nums = [], Set.new
A.times do
  nums << gets.to_i - 1
  areas << gets.split.map{|s| s.to_i - 1}.to_set
end

M, cost, Es = gets.to_i, {}, Array.new(areas.size){Set.new}
M.times do
  a, b, c = gets.split.map(&:to_i); a, b = a - 1, b - 1
  cost[[a, b]], cost[[b, a]] = c, c
  areas.size.times do |ix|
    if areas[ix].member?(a) && areas[ix].member?(b)
      Es[ix] << [a, b]
      break
    end
  end
end

class UnionFind
  def initialize(n)
    @p = Array.new(n, -1)
  end

  def root(x)
    while @p[x] >= 0
      x = @p[x]
    end
    x
  end

  def unite(x, y)
    x, y = self.root(x), self.root(y)
    if x != y
      x, y = y, x if @p[y] < @p[x]
      @p[x] += @p[y]
      @p[y] = x
    end
  end
end

def isST(edges)
  f = UnionFind.new(7)
  edges.each do |a, b|
    return false if f.root(a) == f.root(b)
    f.unite(a, b)
  end
end

spanlist = Hash.new{|h, k| h[k] = []}
nums.sort.each do |num|
  [*0 .. num].combination(2).to_a.combination(num).each{|x| spanlist[num] << x if isST(x)}
end
costlist = []
(0 ... A).each do |ix|
  area = areas[ix]
  lkup = Hash[[*0 ... area.size].zip(area)]
  esum = Es[ix].inject(0){|s, e| s + cost[e]}
  acc = Hash.new(0)
  spanlist[area.size - 1].each do |x|
    plan = esum
    x.each do |a, b|
      v = cost[[lkup[a], lkup[b]]]
      break if v.nil?
      plan -= v
    end
    acc[plan] += 1
  end
  costlist << acc.sort
end
dp = costlist[0]
(1 ... costlist.size).each do |ix|
  acc = Hash.new(0)
  dp.product(costlist[ix]) do |(va, ca), (vb, cb)|
    v, c = va + vb, ca * cb
    acc[v] += c
  end
  acc = acc.sort
  dp, count = [], 0
  acc.each do |v, c|
    count += c
    dp << [v, c]
    break if count >= K
  end
end
dp.sort!
acc, ans = 0, -1
dp.each do |v, c|
  acc += c
  (ans = v; break) if acc >= K
end
puts ans

Submission Info

Judge Result