这个脚本在游戏里面怎么用呢？
TwoSat.make2sat(n, m) 可以生成一个保证有解的2sat问题，n个bool变量m个条件
TwoSat#check_answer(ans) 给出一组解，检查是否可行。
=end
class TwoSat
attr_reader :maxn
attr_accessor :graph
def initialize(n)
@maxn = n
@graph = Array.new(n*2) {[]}
@dfn = Array.new(n*2, 0)
@low = Array.new(n*2, 0)
@scc = Array.new(n*2, 0)
@scc_cnt = 0
@dfn_time = 0
@checked = false @Stk = []
end
def add_condition(x, y, xv, yv)
return if x >= @maxn || y >= @maxn
@graph[(2*x+xv)^1].push(2*y+yv)
@graph[(2*y+yv)^1].push(2*x+xv)
end
def tarjan(u)
@dfn_time += 1
@low = @dfn = @dfn_time
@stk.push(u)
@graph.each do |to|
if @dfn[to] == 0
tarjan(to)
@low = @low[to] if @low[to] < @low
elsif @scc[to] == 0
@low = @dfn[to] if @dfn[to] < @low
end
end
if @low == @dfn
@scc_cnt += 1
while @stk.size != 0
x = @stk.pop
@scc[x] = @scc_cnt
break if x == u
end
end
end
def pre_check
if !@checked
(0...@maxn*2).each do |i|
tarjan(i) if @dfn == 0
end
@checked = true
end
end
def answerable? #检查是否有解
pre_check
(0...@maxn).each do |i|
return false if @scc[i*2] == @scc[i*2+1]
end
return true
end
#检查答案. #一个长度为n的数组描述bool变量0~n-1的取值
def check_answer(ans)
pre_check @mark ||= Array.new(2*@maxn)
@mark.fill(false)
ans.each_with_index do |e, i|
@mark[i*2+e] = true
end
(0...@maxn*2).each do |x|
return false if @mark[x] && !bfs(x)
end
return true
end
def bfs(x)
head = 0
@q ||= Array.new(2*@maxn)
@vis ||= Array.new(2*@maxn)
@q[0] = x
@vis.fill(false)
@vis[x] = true
tail = 1
while(head < tail)
u = @q[head]; head += 1
return false if @mark != @mark[x]
@graph.each do |to|
if !@vis[to]
@q[tail] = to
tail += 1
@vis[to] = true
end
end
end
return true
end
def self.make2sat(n, m) #生成一个n个bool变量，m个条件的2-sat问题
while true
s = self.new(n)
cs = []
m.times do
x = rand(n)
y = rand(n)
#随机构造2-sat
cs << [x, y, rand(2), rand(2)]
s.add_condition(*cs.last)
end
return [s, cs] if s.answerable? #可解
end
end