結果

問題 No.1479 Matrix Eraser
ユーザー 👑 obakyanobakyan
提出日時 2021-05-26 20:12:55
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 1,379 ms / 3,000 ms
コード長 4,722 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 5,120 KB
実行使用メモリ 69,080 KB
最終ジャッジ日時 2024-10-15 15:01:35
合計ジャッジ時間 20,233 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 AC 106 ms
11,688 KB
testcase_08 AC 195 ms
18,260 KB
testcase_09 AC 487 ms
34,324 KB
testcase_10 AC 984 ms
55,652 KB
testcase_11 AC 577 ms
38,292 KB
testcase_12 AC 138 ms
15,192 KB
testcase_13 AC 187 ms
18,520 KB
testcase_14 AC 148 ms
15,832 KB
testcase_15 AC 33 ms
5,888 KB
testcase_16 AC 163 ms
16,596 KB
testcase_17 AC 1,204 ms
63,304 KB
testcase_18 AC 1,217 ms
63,276 KB
testcase_19 AC 1,209 ms
63,280 KB
testcase_20 AC 1,213 ms
63,408 KB
testcase_21 AC 1,187 ms
63,264 KB
testcase_22 AC 1,188 ms
63,276 KB
testcase_23 AC 1,216 ms
63,416 KB
testcase_24 AC 1,233 ms
63,016 KB
testcase_25 AC 1,191 ms
63,276 KB
testcase_26 AC 1,192 ms
63,268 KB
testcase_27 AC 206 ms
17,024 KB
testcase_28 AC 204 ms
17,280 KB
testcase_29 AC 200 ms
17,152 KB
testcase_30 AC 206 ms
17,792 KB
testcase_31 AC 196 ms
17,280 KB
testcase_32 AC 112 ms
10,240 KB
testcase_33 AC 118 ms
9,856 KB
testcase_34 AC 114 ms
9,472 KB
testcase_35 AC 118 ms
10,240 KB
testcase_36 AC 117 ms
10,240 KB
testcase_37 AC 37 ms
5,248 KB
testcase_38 AC 163 ms
12,288 KB
testcase_39 AC 1,379 ms
69,080 KB
testcase_40 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

-- Hopcroft-Karp
ABmatch = {}
ABmatch.create = function(self, an, bn)
  self.dst = {}
  self.edge = {}
  for i = 1, an do
    self.dst[i] = false
    self.edge[i] = {}
  end
  self.src = {}
  self.invcnt = {}
  self.invs = {}
  self.invpos = {}
  self.padded = {}
  for i = 1, bn do
    self.src[i] = false
    self.invs[i] = {}
  end
  self.p = {}
  self.tasks = {}
  self.level = {}
end

ABmatch.addEdge = function(self, a, b)
  table.insert(self.edge[a], b)
  if not self.dst[a] and not self.src[b] then
    self.dst[a] = b
    self.src[b] = a
  end
end

ABmatch.makeAugPath = function(self)
  local tasknum = 0
  local tasks = self.tasks
  local level = self.level
  local edge = self.edge
  local src = self.src
  local an = #self.dst
  local bn = #src
  local invcnt, invs = self.invcnt, self.invs
  local p, psize = self.p, 0
  local padded = self.padded
  local lvinf = an + 1
  for i = 1, an do
    if self.dst[i] then
      level[i] = lvinf
    else
      tasknum = tasknum + 1
      tasks[tasknum] = i
      level[i] = 1
    end
  end
  for i = 1, bn do
    invcnt[i] = 0
    padded[i] = false
  end
  local done = 0
  local lvmax = lvinf
  while done < tasknum do
    done = done + 1
    local a = tasks[done]
    if lvmax < level[a] then break end
    for i = 1, #edge[a] do
      local b = edge[a][i]
      local sb = src[b]
      if sb then
        if level[sb] == lvinf then
          tasknum = tasknum + 1
          tasks[tasknum] = sb
          level[sb] = level[a] + 1
          invcnt[b] = invcnt[b] + 1
          invs[b][invcnt[b]] = a
        elseif level[sb] == level[a] + 1 then
          invcnt[b] = invcnt[b] + 1
          invs[b][invcnt[b]] = a
        end
      else
        if lvmax == lvinf then
          lvmax = level[a]
        end
        if padded[b] then
        else
          padded[b] = true
          psize = psize + 1
          p[psize] = b
        end
        invcnt[b] = invcnt[b] + 1
        invs[b][invcnt[b]] = a
      end
    end
  end
  self.psize = psize
  return lvmax
end

-- ABmatch.dfs = function(self, b, lv)
--   for i = 1, self.invcnt[b] do
--     local a = self.invs[b][i]
--     if self.level[a] == 1 or (self.level[a] == lv and self:dfs(self.dst[a], lv - 1)) then
--       self.dst[a], self.src[b] = b, a
--       self.level[a] = -1
--       return true
--     end
--   end
-- end

ABmatch.restore = function(self, bend, lvend)
  local invs, invcnt, invpos = self.invs, self.invcnt, self.invpos
  local dst, src, level = self.dst, self.src, self.level
  local bn = #src
  for i = 1, bn do
    invpos[i] = 0
  end
  local accept = false
  local tasks = self.tasks
  local taskpos = 1
  tasks[1] = bend
  while 0 < taskpos do
    local b = tasks[taskpos]
    if accept then
      local a = invs[b][invpos[b]]
      dst[a], src[b] = b, a
      level[a] = -1
      taskpos = taskpos - 1
    else
      if invpos[b] == invcnt[b] then
        taskpos = taskpos - 1
      else
        local ip = invpos[b] + 1
        invpos[b] = ip
        local a = invs[b][ip]
        if level[a] == 1 then
          accept = true
          dst[a], src[b] = b, a
          level[a] = -1
          taskpos = taskpos - 1
        elseif level[a] + taskpos == lvend + 1 then
          taskpos = taskpos + 1
          tasks[taskpos] = dst[a]
        end
      end
    end
  end
end

ABmatch.matching = function(self)
  local an = #self.dst
  local lv = self:makeAugPath()
  while lv <= an do
    for i = 1, self.psize do
      self:restore(self.p[i], lv)
      -- self:dfs(self.p[i], lv)
    end
    lv = self:makeAugPath()
  end
  self.executed = true
end

ABmatch.getMatchCount = function(self)
  if not self.executed then
    self:matching()
  end
  local cnt = 0
  for i = 1, #self.dst do
    if self.dst[i] then cnt = cnt + 1 end
  end
  return cnt
end

ABmatch.new = function(an, bn)
  local obj = {}
  setmetatable(obj, {__index = ABmatch})
  obj:create(an, bn)
  return obj
end

local h, w = io.read("*n", "*n")
local t = {}
for i = 1, h do
  for j = 1, w do
    local a = io.read("*n")
    if 0 < a then
      if not t[a] then t[a] = {} end
      table.insert(t[a], i)
      table.insert(t[a], j)
    end
  end
end

local ret = 0
for _k, tbl in pairs(t) do
  local rowcnt = 0
  local rowmap = {}
  for i = 1, #tbl, 2 do
    local r = tbl[i]
    if not rowmap[r] then
      rowcnt = rowcnt + 1
      rowmap[r] = rowcnt
    end
  end
  local colcnt = 0
  local colmap = {}
  for i = 2, #tbl, 2 do
    local c = tbl[i]
    if not colmap[c] then
      colcnt = colcnt + 1
      colmap[c] = colcnt
    end
  end
  local abm = ABmatch.new(rowcnt, colcnt)
  for i = 1, #tbl, 2 do
    abm:addEdge(rowmap[tbl[i]], colmap[tbl[i + 1]])
  end
  ret = ret + abm:getMatchCount()
end
print(ret)
0