Lv3.寻梦者
您需要 登录 才可以下载或查看,没有帐号?注册会员
=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) 给出一组解,检查是否可行。 =endclass 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 =begins = TwoSat.new(2) #两个bool变量s.add_condition(1, 0, 1, 1) #添加约束 b(0)为真 || b(1)为真puts s.answerable? #是否有解 trueputs s.check_answer([1, 1]) #检查b(0) = 1, b(1) = 1是否可行 trueputs s.check_answer([1, 0]) #检查b(0) = 1, b(1) = 0是否可行 trueputs s.check_answer([0, 1]) #检查b(0) = 0, b(1) = 1是否可行 trueputs s.check_answer([0, 0]) #检查b(0) = 0, b(1) = 0是否可行 false=end
=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
查看全部评分
使用道具 举报
本版积分规则 发表回复 回帖后跳转到最后一页
折叠内容标题(非必须)
折叠内容
站长信箱:[email protected]|手机版|小黑屋|无图版|Project1游戏制作
GMT+8, 2024-3-29 20:57
Powered by Discuz! X3.1
© 2001-2013 Comsenz Inc.