插头DP（连通性状态压缩DP）

What · 是什么

插头DP（连通性状态压缩DP）是轮廓线DP的推广：在处理格子 (i,j) 时，轮廓线是已决策与未决策格子之间的分界线，状态记录轮廓线上每个位置'是否有插头（与相邻格的连接）'以及插头之间的连通性。一条回路问题时插头总是成对出现，合法状态构成括号序列。常用两种编码：括号表示（'(' ')' 配对）与最小表示（连通分量用最小可用数字标记）。多数回路问题只需要记录插头是否存在（如 Eat the Trees 多回路覆盖），而单回路问题（Formula 1、Ural 1519）必须区分连通性以禁止提前形成小环。状态可用哈希表/字典存储（合法状态稀疏），行末滚动 roll() 把最后一列左插头移到行首。转移分四类：左、上均有插头（合并或闭合）、恰有一个插头（延伸或转向）、均无插头（新建一对插头）、以及障碍格处理。

Why · 为什么

How · 实现

伪代码

# 单回路覆盖 n*m 棋盘（最小表示 + 哈希表/字典）
cur = {encode(all-0轮廓): 1}
for i in 0..n-1:
  for j in 0..m-1:
    nxt = {}
    for state in cur:
      decode(state) -> b[]
      lt, up = b[j], b[j+1]
      if 障碍格: 若 lt==0 且 up==0 则直接保留; continue
      if lt and up:
        if lt==up:
          if 最后一格且其余全0: nxt[all-0] += val
        else: 合并连通块(把 lt 全部改成 up), 置 b[j]=b[j+1]=0
      elif lt or up:
        t = lt|up
        if 右格开放: 延伸 b[j+1]=t, b[j]=0
        if 下格开放: 延伸 b[j]=t, b[j+1]=0
      else:
        if 右与下均开放: b[j]=b[j+1]=新编号(成对新插头)
    cur = 最小表示去重合并后的 nxt
  行末 roll(): 要求 b[m]==0, 去掉 b[m] 并在头部补 0
答案 = cur 中全 0 状态的计数

Python 实现

# -*- coding: utf-8 -*-
# 插头DP 单回路覆盖 n*m 棋盘（含障碍），最小表示编码，返回方案数
from collections import defaultdict


def encode(b):
    """轮廓线数组 -> 最小表示整数编码（tuple）"""
    mp, out, nxt = {}, [], 1
    for x in b:
        if x == 0:
            out.append(0)
        else:
            if x not in mp:
                mp[x] = nxt
                nxt += 1
            out.append(mp[x])
    return tuple(out)


def plug_dp(n, m, open_cells):
    """open_cells: {(r,c)} 0-indexed 可走的格子。返回用一条回路覆盖所有开放格子的方案数。"""
    cur = {encode([0] * (m + 1)): 1}
    last_open = max(r * m + c for (r, c) in open_cells)
    for r in range(n):
        for c in range(m):
            idx = r * m + c
            is_cell = (r, c) in open_cells
            is_last = idx == last_open
            nxt = defaultdict(int)
            for state, val in cur.items():
                b = list(state)
                left, up = b[c], b[c + 1]
                if not is_cell:                     # 障碍格
                    if left == 0 and up == 0:
                        nxt[encode(b)] += val
                    continue
                if left and up:
                    if left == up:                  # 闭合：必须最后一格且其余全 0
                        if is_last:
                            bb = list(b); bb[c] = bb[c + 1] = 0
                            if all(x == 0 for x in bb):
                                nxt[encode(bb)] += val
                    else:                            # 合并两个连通块
                        bb = list(b); bb[c] = bb[c + 1] = 0
                        for i in range(m + 1):
                            if bb[i] == left:
                                bb[i] = up
                        nxt[encode(bb)] += val
                elif left or up:
                    t = left | up
                    if c + 1 < m and (r, c + 1) in open_cells:   # 向右延伸
                        bb = list(b); bb[c] = 0; bb[c + 1] = t
                        nxt[encode(bb)] += val
                    if r + 1 < n and (r + 1, c) in open_cells:   # 向下延伸
                        bb = list(b); bb[c] = t; bb[c + 1] = 0
                        nxt[encode(bb)] += val
                else:                               # 新建一对插头（成对生成）
                    if (c + 1 < m and (r, c + 1) in open_cells
                            and r + 1 < n and (r + 1, c) in open_cells):
                        bb = list(b); bb[c] = m + 1; bb[c + 1] = m + 1
                        nxt[encode(bb)] += val
            cur = nxt
        # 行末滚动：最后一列左插头必须为 0，去掉后整体左移一位
        roll = defaultdict(int)
        for state, val in cur.items():
            bb = list(state)
            if bb[m] != 0:
                continue
            del bb[m]
            bb.insert(0, 0)
            roll[encode(bb)] += val
        cur = roll
    return cur.get(encode([0] * (m + 1)), 0)


if __name__ == '__main__':
    def all_open(n, m):
        return {(r, c) for r in range(n) for c in range(m)}
    # 与暴力枚举对拍的小规模值
    assert plug_dp(2, 2, all_open(2, 2)) == 1
    assert plug_dp(2, 3, all_open(2, 3)) == 1
    assert plug_dp(3, 3, all_open(3, 3)) == 0   # 3x3 无单回路
    assert plug_dp(3, 4, all_open(3, 4)) == 2
    assert plug_dp(2, 4, all_open(2, 4)) == 1
    # 中心有障碍的 3x3：绕开中心仍有一条回路
    oc = all_open(3, 3) - {(1, 1)}
    assert plug_dp(3, 3, oc) == 1
    print('plug-dp tests passed')

易错点

• 单回路问题必须区分插头连通性（最小表示/括号），否则会算入多个小环
• 左、上均有插头且同连通块时闭合会成环，只能允许在最后一个空格闭合
• 行末 roll 时若最后一列左插头非 0 则该状态非法，必须丢弃
• 障碍格必须延续状态（left==0 且 up==0 才合法），且不做插头生成
• 最小表示编码的重新标号必须从 1 开始且 0 保留（0 表示无插头）
• 新建一对插头时两者要用同一新编号（保证连通），否则合并判定出错
• m 较大时 Python 字典 + tuple 编码会超时/爆内存，需手写哈希与位编码

例题

信源

• OI Wiki✓ https://oi-wiki.org/dp/plug/
• 书籍✓ OI Wiki 插头DP 三类模板（Eat the Trees / Formula 1 / 单路径）