算法分析与题解

问题转化与建模

这是一个典型的二分图最小点覆盖问题，通过巧妙的建模转化为图论问题：

1. 节点定义：

   • 对于每个黑色格子（1），它可以产生两种题目：
     • 水平题目（向右）：如果右边是白色格子（0）
     • 竖直题目（向下）：如果下面是白色格子（0）

2. 边表示：

   • 每个白色格子（0）被两个题目覆盖：从它左边的黑色格子开始的水平题目，和从它上面的黑色格子开始的竖直题目
   • 将每个白色格子视为一条边，连接着覆盖它的水平题目节点和竖直题目节点

3. 目标：

   • 选择最少数量的题目节点，使得所有的边（白色格子）都被覆盖
   • 这正是二分图的最小点覆盖问题

算法核心：König 定理

1. 二分图构建：

   • 左部：所有可能的水平题目
   • 右部：所有可能的竖直题目
   • 边：每个白色格子连接对应的水平题目和竖直题目

2. König 定理应用：

   • 定理：在二分图中，最小点覆盖数 = 最大匹配数
   • 求解步骤：
     1. 求二分图的最大匹配（匈牙利算法）
     2. 根据最大匹配构造最小点覆盖

3. 构造最小点覆盖：

   • 从所有未匹配的左部节点出发，进行 DFS/BFS 寻找交错路径
   • 标记所有访问到的节点
   • 最小点覆盖 = 左部未标记的节点 ∪ 右部已标记的节点

代码实现关键点

1. 编号方案：

   • id(0, i, j)：水平题目编号
   • id(1, i, j)：竖直题目编号
   • 统一在 [1, n*m] 和 [n*m+1, 2*n*m] 范围内编号

2. 建图优化：

   • 对于每个白色格子，连接它左边的黑色格子的水平题目和上面的黑色格子的竖直题目
   • 使用 row[i] 和 col[j] 记录每行/列最近的黑色格子

3. 匈牙利算法：

   • 在左部节点（水平题目）上进行增广路搜索
   • 使用 bitset 优化访问标记

4. 构造覆盖集：

   • 从所有未匹配的右部节点（竖直题目）出发进行标记
   • 根据标记情况输出对应的题目

时间复杂度

• 节点数：$O(nm)$
• 边数：$O(nm)$
• 匈牙利算法：$O(nm \cdot \text{匹配数})$，在 $n,m \le 500$ 时可行

算法标签

#二分图 #最小点覆盖 #König定理 #匈牙利算法 #图匹配
#网络流 #图论建模 #组合优化

样例验证

以样例1为例：

4 5
11111
10000
10000
10000

• 白色格子集中在第2-4行的第2-5列
• 所有白色格子只能被水平题目覆盖
• 最小点覆盖 = {第2行水平题, 第3行水平题, 第4行水平题}
• 输出：3个DESNO题目

总结

本题的关键在于将填字游戏的覆盖问题转化为二分图模型，利用 König 定理将最小点覆盖问题转化为最大匹配问题，通过匈牙利算法高效求解。这种"问题转化+经典算法"的组合是编程竞赛中的常见解题模式。