=begin
描述：
n个布尔型变量b(0), b(1), ..., b(n-1) 。m个条件，用0表示假，用1表示真。
每个条件形如
b(x)为真/假 或者 b(y)为真/假
求一组符合所有条件的解(注：有可能无解)
这个脚本在游戏里面怎么用呢？
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
[url=home.php?mod=space&uid=33409]@Stk[/url] = []
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[u] = @dfn[u] = @dfn_time
@stk.push(u)
@graph[u].each do |to|
if @dfn[to] == 0
tarjan(to)
@low[u] = @low[to] if @low[to] < @low[u]
elsif @scc[to] == 0
@low[u] = @dfn[to] if @dfn[to] < @low[u]
end
end
if @low[u] == @dfn[u]
@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[i] == 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
[url=home.php?mod=space&uid=25204]@mark[/url] ||= 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[u] != @mark[x]
@graph[u].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
end
=begin
s = TwoSat.new(2) #两个bool变量
s.add_condition(1, 0, 1, 1) #添加约束 b(0)为真 || b(1)为真
puts s.answerable? #是否有解 true
puts s.check_answer([1, 1]) #检查b(0) = 1, b(1) = 1是否可行 true
puts s.check_answer([1, 0]) #检查b(0) = 1, b(1) = 0是否可行 true
puts s.check_answer([0, 1]) #检查b(0) = 0, b(1) = 1是否可行 true
puts s.check_answer([0, 0]) #检查b(0) = 0, b(1) = 0是否可行 false
=end
2sat.zip
(1.39 KB, 下载次数: 89)