问题定义
从选择开始
题目要求确定一个集合：集合中的每个元素是一个好座位， 集合规模应尽量大，并且不能包含任何一对会作弊的座位。以下使用一个仅有四个好座位的教室 展示合法选择与冲突选择。
选择 A 后，后续判断只需确认 B、E 的可选状态。 座位的颜色、面积、离讲台多远，都与判断无关。
A 与 B 不能共存A 与 E 不能共存因而问题的最小信息单位不是“方向”，而是一对不能同时出现的选择。
选一种语言
换成冲突
一种实现是在每次选座时重新检查六个方向，另一种实现是保存一个 “谁和谁冲突”的二维表。但二者都在表达同一件事：两个对象之间存在一种关系。 图正是专门保存“对象 + 两两关系”的结构。
枚举全部集合
用二进制位表示座位是否被选，再逐个检查集合是否合法。
回溯并即时检查
按座位递归执行“选或不选”，一旦出现方向冲突就提前停止分支。
预存冲突关系
先计算不能共存的座位对，再用图保存对象与两两关系。
按需展开方案 A、B 具体怎样实现？包含伪代码、剪枝过程和“重复检查”的翻转演示
枚举全部集合
- 给 g 个好座位编号 0 到 g−1。
- 用一个 g 位二进制数表示座位集合。
- 对集合中的每个座位检查六个冲突方向。
- 集合合法时，用选中位数更新答案。
best = 0
for mask in [0, 2^g):
valid = true
for seat in mask:
if 六个方向中存在已选座位:
valid = false
if valid:
best = max(best, popcount(mask))解决：能够得到正确答案。
痛点：需要检查 2ᵍ 个集合，规模增长时计算量迅速失控。
回溯并即时检查
- 递归处理第 i 个好座位。
- 分为“不选”和“选”两个分支。
- 选择前检查六个方向；冲突时立即剪枝。
- 到达末尾时统计当前人数。
search(i, chosen):
if i == g:
updateAnswer(chosen)
return
search(i + 1, chosen) // 不选
if seat[i] 与 chosen 不冲突:
search(i + 1, chosen + seat[i])解决：非法方案不必继续展开。
剩余痛点：最坏情况仍为 2ᵍ，而且。
冲突图
边不是路线，是“禁止同时选择”
A—B 表示二者不能一起坐人。边没有方向，因为不管是谁看见谁，最终限制都是 “这一对不能同时出现”。
- A—B、E—F：左右冲突
- A—E、B—F：斜向冲突
- B 与 E：正前后，不冲突，所以不连边
独立集
图中挑出一些点，若这些点之间一条边也没有，它们就是一个独立集。 在本题里，它就是一份合法座位安排；最大的那份叫最大独立集。
基础方案
直接求
在尚未利用图结构时，最直接的算法是对每个座位做一次二选一： “选”或者“不选”。选的时候检查它是否与已选点冲突，最后记录人数最大值。
接着还要为 E、F 继续分支。冲突检查能剪掉一些枝条，却没有改变最坏情况下的指数增长。
种可能的座位集合，也就是 2^20。
支线详解逐行状态压缩 DP 怎样复用上一行？位掩码、合法状态、两行兼容表与一次完整转移
另一条完整路线
逐行状态压缩 DP
枚举全部座位需要 2ᵐⁿ 个集合。题目中每行只有 n≤8 个座位， 因此可以只记录“当前行怎样坐”，并复用上一行已经计算出的最优结果。 这项优化针对的是大量集合拥有相同“行状态”的重复计算。
usable[row]表示第 row 行可用座位的 n 位二进制掩码。与第 c 列对应的位为 1，表示 (row,c) 是可用座位 .；对应位为 0，表示该位置是坏座位#。为使位串与座位图从左到右对齐，以下示例规定最高位对应第 0 列。
usable = 110合法：000、100、010usable = 011合法：000、010、001cur & ~usable[row] == 0~usable 的 1 位对应坏座位；与 cur 相交为 0，说明没有选择坏座位。cur & (cur << 1) == 0cur & (prev << 1) == 0cur & (prev >> 1) == 0dp[row][cur]处理到当前行，并使用 cur 排列时的最多学生数。
dp[row][cur] = max(dp[row−1][prev]) + popcount(cur)只从与 cur 没有斜向冲突的 prev 转移。
把“两行两两检查”拆开
检查的是两种“整行坐法”能否上下拼接
上一行的每一种合法状态记为 prev，当前行的每一种合法状态记为cur。从两个集合中各取一个，检查它们之间有没有斜向冲突。 不是把两行中的每个座位重新两两比较。
000 100(A) 010(B)000 010(E) 001(F)| prev ＼ cur | 000 | 010（E） | 001（F） |
|---|---|---|---|
| 000 | ✓ | ✓ | ✓ |
| 100（A） | ✓ | × A—E | ✓ |
| 010（B） | ✓ | ✓ | × B—F |
A 在 E 的左上方，学生可以互相看到，所以这一对状态不能连接。
B 与 E 正前后相邻；题目明确说看不到正前方或正后方，因此允许。
3 个 prev 分别尝试搭配 3 个 cur，共检查 3×3=9 个状态对。
例如计算 dp[1][010(E)]：
每行最多有 2ⁿ 种状态；上一行至多 2ⁿ 种，当前行也至多 2ⁿ 种， 组合起来是 2ⁿ×2ⁿ=4ⁿ。n≤8 时，每相邻两行最多检查 256×256 个“整行状态对”，因此该方案能够直接解决本题。
二分结构验证
找结构
前面已经把每个好座位表示为一个点，把每一对“不能同时坐”的座位表示为一条冲突边。 因此，一份合法座位安排就是冲突图中的独立集。建模完成后，问题变成了 “如何求这张图的最大独立集”。一般图上的最大独立集仍然难以高效求解， 所以这一章不急着套算法，而是回到题目的四种冲突方向，寻找它们共同遵守的规律。
现在卡在哪里
换成冲突图，不等于已经变简单
冲突图只是把题意保存得更统一。若它是一张任意的普通图， “每个点选或不选”仍可能产生 2ᵛ 个状态，最大独立集依然难求。
一般图最大独立集 → 仍可能指数级准备寻找什么
用简单标签压缩“谁会与谁冲突”
若能给座位贴一个很简单的标签，并让每条冲突边都连接不同标签， 那么同标签内部便完全没有冲突，整张图的关系只需在标签之间检查。 这还不是答案，但它会把任意连接压缩成更规整的连接模式。
目标不是先规定“两组”，而是先寻找能预测每条边的稳定标签规律自然产生分组
四种方向共同指向列奇偶
左、右、左上、右上的列变化全部是 ±1；加减 1 又必定让奇偶性翻转。 因而标签自然取 col % 2，它恰好只有 0、1 两种值。 两组不是预先指定的目标，而是这个稳定规律产生的结果。
Δcol = ±1 → col % 2 必定从 0 ↔ 1验证成功能得到什么
先验证所有边，再给结构命名
若所有冲突边都从偶数列连到奇数列，组内就没有冲突边。到这一步我们只确认了事实； 这种“顶点能分成两组且边只跨组”的图，下一章再正式命名并研究。
发现规律 → 提出分组 → 审计每类边 → 确认结构扩展比较什么是棋盘色？为什么它在这里会失败？展开查看 (row + col) % 2 的染色方式
棋盘染色
上下左右换色，斜向保持同色
像国际象棋棋盘一样，让上下左右相邻的格子黑白交替。 坐标为 (row, col) 的格子颜色由 (row + col) 的奇偶决定。
斜向移动会同时改变行和列，行列和改变 0 或 2，因此斜向冲突的两个座位 仍会落在同一颜色组。这正是棋盘色在本题失败的原因。
是否能分成两组仍需验证，不能直接假定成立。下面依次检查按行、 棋盘色和按列三种自然染色，并将留在组内的冲突边标红。
不会。左右冲突的两个座位行号相同，Δrow = 0，因此仍在同一组。
同一行的座位被染成同色，因此左右相邻的冲突边会留在组内。
失败：A—B、E—F 都留在同一组。
Δcol 全部为 ±1→列号奇偶必定翻转→每条冲突边都跨组扩展证明审计 A—B、A—E、B—F、E—F 四条冲突边同时说明为什么结论适用于更大的教室
最终证明
不能只看示意图：逐条审计所有冲突边
使用 group = col % 2 后，偶数列进入第 0 组，奇数列进入第 1 组。 下面确认示例中的每一条边都跨组。
0 → 1偶 → 奇跨组 ✓0 → 1偶 → 奇跨组 ✓1 → 2奇 → 偶跨组 ✓1 → 2奇 → 偶跨组 ✓题目的四种作弊方向分别是(0,-1)、(0,+1)、(-1,-1)、(-1,+1)。 它们的列变化全部是 ±1，所以任意冲突边都会翻转列号奇偶。 证明依赖的是全部冲突方向的共同性质，而不是这个四座位示例碰巧成功。
图论基础概念
二分图
上一章不是先猜“二分图”，而是先从 Δcol = ±1 推出了列奇偶分组。 现在才暂停解题，研究这种结构本身。 图经常描述“两类对象之间的关系”：候选人与岗位、飞行员与飞机、用户与商品。 如果关系只会发生在两类对象之间，而不会发生在同一类内部，就应该把这条共同结构保留下来。二分图正是为这种“两岸关系”准备的模型。
候选人只连接岗位，岗位只连接候选人。边表示“可以录用”，同类对象之间不需要连边。
候选人 ↔ 岗位座位都是同一种对象，但每次冲突都会让列号奇偶翻转，因此可以按偶数列、奇数列分岸。
偶数列 ↔ 奇数列正式定义
不是“画成两列”，而是顶点真的能够这样划分
对图 G = (V,E)，如果能找到两个互不相交的集合L、R，使全部顶点恰好属于其中一侧， 而每条边都在左右两侧各取一个端点，那么 G 是二分图。
V = L ∪ R全部顶点都被分进去L ∩ R = ∅一个顶点不能同时属于两侧E ⊆ L × R每条边只能跨越两侧回到座位图验证定义
L 放偶数列，R 放奇数列
图的边仍是 A—B、A—E、F—B、F—E，只是把同组节点搬到一起。 A、F 之间没有边，B、E 之间也没有边；四条边全部跨越两侧。
三种等价语言
分组、二染色、没有奇环，说的是同一件事
做题时不一定直接看见 L、R。更常见的方法是尝试二染色； 一旦染色失败，沿冲突路径会还原出一个奇数长度的环。
这并不代表可以把两组分别求解；跨组边仍然把两侧绑在一起。 真正的收益是关系只能在两岸之间交替，后续的匹配与点覆盖定理因此有了成立前提。
扩展性质二分图还具备哪些常见性质？不影响座位题主线，可在建立基本定义后再读
L 内部、R 内部都没有边。但这不等于可以忽略另一侧：跨组边仍然限制两侧能否同时选择。
树没有环；偶环可以交替染色。任何子图也会继续保持二分性。
起点染成 0 或 1 会得到两份互换的答案；非连通图的每个连通分量都可以独立交换两色。
“二分”只规定哪些边允许出现，并不要求全部出现；全部 m×n 条跨组边都存在时才叫完全二分图。
通用判定不知道分组时，怎样用 BFS / DFS 找出 L、R？逐个连通分量二染色，时间复杂度 O(V + E)
- 找到一个尚未染色的点，把它染成 0，作为新连通分量的起点。
- 用 BFS 或 DFS 遍历边；每遇到未染色邻点，就染成当前点的相反颜色。
- 若一条边的两端已经是同色，立即失败；这条边与搜索树路径共同形成奇环。
- 一个分量完成后继续寻找未染色点，直到所有顶点都被处理。
for each uncolored start:
color[start] = 0
push(start)
while queue not empty:
u = pop()
for v in neighbors[u]:
if color[v] is unset:
color[v] = color[u] xor 1
push(v)
else if color[v] == color[u]:
return false
return true每个顶点至多入队一次，每条边检查常数次，所以总复杂度是O(|V| + |E|)。本题不必实际跑染色，因为“列号奇偶”已经直接给出了颜色。
扩展地图二分结构还能优化哪些问题？九类问题逐项查看；本文主线只使用最大独立集、点覆盖与匹配
为什么值得专门命名
同一个简单限制，会让一批问题出现更强的结论
二分图没有组内边、没有奇环，路径会稳定地在两侧交替。 这使有些问题直接变成常数级结论，有些问题能统一归约到最大匹配。 点击下面的概念，只显示一项详细解释。
最小点覆盖
τ(G) = ν(G)选择最少的点，使每条边至少碰到一个被选点。
在二分图中，柯尼希定理保证最小点覆盖数等于最大匹配数；一般图没有这个等式。
匹配给出覆盖所需点数的下界，而二分结构保证这个下界一定能够达到。
撤下尽量少的座位消除全部作弊冲突，正是本文的问题。
资料来源本章的定义、性质和应用依据OI Wiki、MIT、Cornell、NetworkX 与 MathWorld
转化视角
撤下谁
先暂时忘掉“点覆盖”这个词。假设 A、B、E、F 四个好座位一开始全部坐了学生， 此时存在 A—B、A—E、B—F、E—F 四组作弊冲突。 我们不直接猜最终该保留谁，只做一个更具体的动作：撤下一名学生，看看哪些冲突随之消失。
做完动作，再给它命名
被撤下的 {B,E}，在图论中就是一个点覆盖
“点”是因为我们选择的是座位点 B、E，不是选择冲突边；“覆盖”是因为每一条冲突边都至少碰到一个被撤下的端点。 例如 A—B 碰到 B，A—E 碰到 E，所以这两条冲突都会被破坏。
A、B、E、F 是四个点；被选入点覆盖的点，在本题里表示准备撤下的座位。
对 A—B，只撤 A、只撤 B、或两者都撤都能消除冲突；A、B 都保留才会出问题。
只要漏掉一条边，剩下的学生中就仍有一对会作弊，因此还不是合法安排。
这两条边没有公共端点。无论只撤下哪一个座位，都最多消除其中一条，另一条仍然存在。 所以至少要撤下 2 个座位。
“至少要 2 个”和“确实能用 2 个做到”同时成立，因此 {B,E}是一个最小点覆盖。{A,F} 也是另一份最优答案。
扩展抽象把刚才的撤座过程写成集合与公式先理解具体例子，再看 V、E、C 与补集关系
V = {A,B,E,F}：全部好座位C = {B,E}：被撤下的座位V \ C = {A,F}：最终保留的座位每条 {u,v} ∈ E，都有 u ∈ C 或 v ∈ C最小化 |C| 就是在尽量少撤座；总座位数 |V| 固定，所以 |C| 越小， 保留下来的 |V| − |C| 就越大。
集合关系图
撤下区与保留区恰好互补
红色集合 C 负责碰到每条冲突边；剩余的 V \ C 内部便不可能再有冲突边，因此它是独立集。
柯尼希定理
从覆盖到匹配
点覆盖仍然在“从很多点中找最少的一组”。先寻找一个容易验证的下界： 如果挑出若干条互不共享端点的冲突边，那么每条边都必须由不同的撤下座位负责。 挑出的这组边越多，对“至少要撤下多少点”的约束就越强——这正是引入匹配的原因。
A—B 与 F—E 可以同时选，因为四个端点互不重复；A—B 与 A—E 不能同时选，因为它们都占用了 A。
匹配选择的是“冲突边”，不是最终保留的座位。它在这里用来证明至少需要撤下多少点。
若匹配中有 k 条互不共享端点的边，点覆盖至少需要 k 个点，所以任何图都有最大匹配数 ≤ 最小点覆盖数。二分图的特殊之处，是这个下界一定能恰好达到。
术语对照区分独立集、点覆盖、匹配和最大流最终选择的是座位点，匹配选择的是冲突边
点与点之间没有冲突边；这才是最终的学生安排。
每条冲突边至少碰到一个被撤下的点，与独立集互为补集。
它不是座位方案，而是用来计算“至少需要撤下多少点”。
流量不是学生人数；一单位流代表一条匹配边。
柯尼希定理图解
同一个“2”，在二分图中可以从边落到点
左、中两幅使用同一张二分冲突图；右侧三角形则展示一般图为什么不能保证等号。
展开证明：为什么任何图只有 ≤，二分图却能取等号？
匹配边之间没有公共端点。每条匹配边都必须被覆盖， 一个覆盖点不能同时处理两条端点完全分离的匹配边，所以至少需要同样多的点。
所有边只跨越左右两岸后，可以利用交替路径， 从最大匹配构造出数量完全相同的点覆盖。
三角形最多只能选一条匹配边，却至少需要两个点覆盖三条边，因此没有等号保证。
设最大匹配为 M。从左组所有未匹配点出发，只按照“左到右走非匹配边、 右到左走匹配边”的规则寻找交替路径，把能够到达的点记为 Z。
最终选择“左组中不在 Z 的点”与“右组中位于 Z 的点”，即(L − Z) ∪ (R ∩ Z)。这个集合会覆盖所有边，并且恰好从每条匹配边 取一个端点，因此点数等于匹配数。这一步依赖所有边只能在左右两组之间连接。
流网络建模
变成流
上一章已经把答案缩减为“求二分图最大匹配”，但定理本身还不是执行过程。 我们需要一种机制同时保证：每条候选冲突边可以被选择，而每个座位最多参加一次匹配。 网络流用容量统一表达这些限制，因此成为这里的计算工具。
目标是让从源点 S 到汇点 T 的总流量尽可能大。
方向在这里组织计算步骤，不一定是原问题中的真实方向。
边上的当前流量不能超过容量；容量 1 表示最多使用一次。
一单位流必须走完 S 到 T 的完整路径，不能在座位点凭空消失。
第一张图：描述题目
冲突图点是座位无向边表示两个座位不能同时保留第二张图：执行算法
流网络保留原来的座位点，并增加人工节点 S、T有向边负责限制一个座位最多参加一次匹配扩展机制算法怎样继续找路，又怎样撤回旧选择？增广路与残量网络是实现细节，不影响先理解建模
为使“一单位流”恰好对应“一条匹配边”，需要添加三种不同含义的边：
S → 每个左组座位，容量 1
人工入口边，不代表冲突；保证一个左侧座位最多参与一次匹配。左组 → 有冲突的右组，容量 1
由原来的冲突边改成有向边；只有这一段仍然对应真实冲突。每个右组座位 → T，容量 1
人工出口边，不代表冲突；保证一个右侧座位最多参与一次匹配。Dinic 的执行过程与完整 C++
Dinic 反复做两件事：BFS 给节点分层，只保留向下一层前进的边； DFS 在分层图里尽量推流。推不动后重新 BFS，直到 T 不可达。 反向边负责“撤回并改配”，这正是贪心匹配可能选错时的纠错机制。
class Solution {
struct Edge { int to, rev, cap; };
vector<vector<Edge>> g;
vector<int> level, cur;
void addEdge(int u, int v, int cap) {
g[u].push_back({v, (int)g[v].size(), cap});
g[v].push_back({u, (int)g[u].size() - 1, 0});
}
bool bfs(int s, int t) {
fill(level.begin(), level.end(), -1);
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto &e : g[u]) {
if (e.cap && level[e.to] == -1) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return level[t] != -1;
}
int dfs(int u, int t, int f) {
if (u == t) return f;
for (int &i = cur[u]; i < (int)g[u].size(); ++i) {
Edge &e = g[u][i];
if (e.cap && level[e.to] == level[u] + 1) {
int pushed = dfs(e.to, t, min(f, e.cap));
if (pushed) {
e.cap -= pushed;
g[e.to][e.rev].cap += pushed;
return pushed;
}
}
}
return 0;
}
int maxFlow(int s, int t) {
int result = 0;
while (bfs(s, t)) {
fill(cur.begin(), cur.end(), 0);
while (int pushed = dfs(s, t, INT_MAX))
result += pushed;
}
return result;
}
public:
int maxStudents(vector<vector<char>>& seats) {
int m = seats.size(), n = seats[0].size();
int S = m * n, T = S + 1;
g.assign(m * n + 2, {});
level.resize(m * n + 2);
cur.resize(m * n + 2);
int good = 0;
auto id = [n](int r, int c) { return r * n + c; };
int dr[6] = {0, 0, -1, -1, 1, 1};
int dc[6] = {-1, 1, -1, 1, -1, 1};
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
if (seats[r][c] == '#') continue;
++good;
int u = id(r, c);
if (c % 2 == 0) {
addEdge(S, u, 1);
for (int k = 0; k < 6; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& seats[nr][nc] == '.') {
addEdge(u, id(nr, nc), 1);
}
}
} else {
addEdge(u, T, 1);
}
}
}
return good - maxFlow(S, T);
}
};适用条件
何时能用
本题走的是“冲突图 → 二分图 → 匹配 → 网络流”，但这只是网络流的一条入口， 不是所有网络流题都先找二分图。判断新题时，先看自己正在解决哪一种困难，再选择对应路线。
二分图 → 最大匹配 → 最大流二分性是匹配定理和三层流网络成立的前提。
容量网络 → 最大流 / 最小割运输、通信、切割不要求原图是二分图。
明确一个点代表人、座位、任务、机器还是格点。
不能共存、可以匹配、需要切断，决定边的语义。
若要套二分匹配，需进行二染色验证；一般运输网络则跳过此项。
每人一次用 1，多份名额用 k，代价另需最小费用流。
每单位流必须能还原成一个合法决策，反之也能构造成流。
如果加入前后冲突
上下座位列差为 0，会落在同一列奇偶组。不过若只有上下左右冲突， 可改用 (row + col) % 2 的棋盘染色。
如果八个方向都冲突
三个相邻座位可以形成三角形。三角形无法只用两种颜色染开， 最大匹配也不再等于最小点覆盖。
扩展迁移把同一套建模方法迁移到其他领域招聘、排班、运输与最小割；一次展开一个具体问题
同一工具的其他题目
先辨认“一单位流”代表什么
下面四类问题都能画成流网络，但边的含义并不相同。展开卡片可查看题意、 建模方式和一个具体答案。
招聘候选人与岗位的一对一最大匹配一单位流 = 录用一个人并分配一个岗位
题目
有 3 名候选人和 3 个岗位。每个人只能入职一个岗位，每个岗位只有 1 个名额，而且只能把候选人分配到他胜任的岗位。求最多能录用多少人。
建模
- S → 每位候选人，容量 1：一个人最多被录用一次。
- 候选人 → 能胜任的岗位，容量 1：只允许合法分配。
- 每个岗位 → T，容量 1：一个岗位最多录用一人。
答案
最大流为 3。一种方案是 A→后端、B→Android、C→测试，因此三人都能录用。
胜任关系
| 候选人 | Android | 后端 | 测试 |
|---|---|---|---|
| A | ✓ | ✓ | — |
| B | ✓ | — | — |
| C | — | ✓ | ✓ |
S→1候选人→1岗位→1T排班员工与班次的容量分配一单位流 = 一名员工承担一个班次
题目
已知每名员工可以上哪些班次、每人最多工作几班，以及每个班次需要几人， 求最多能填补多少个值班名额。
解决方案
S→员工的容量设为该员工最多可上班次数；员工→可用班次连边； 班次→T 的容量设为该班次需求人数。最大流就是最多填补的名额数。 若还要尽量满足偏好，可把偏好转成费用，改用最小费用最大流。
运输边容量限制下的最大运输量一单位流 = 一单位货物或数据
题目
仓库到门店之间有若干中转站和道路，每条道路每天最多运输一定数量， 求一天最多能从仓库送多少货到门店。
解决方案
仓库直接作为 S，门店作为 T，道路就是带容量的边，求最大流即可。 若限制的是中转站吞吐量，可把一个站拆成入点和出点，并在两点之间连一条容量边。
切割最小代价切断源点与汇点最大流值 = 最小割容量
题目
每条通信线路都有切断代价，希望用最小总代价，使攻击源 S 再也无法把信息传到 核心服务器 T。
解决方案
把切断代价作为边容量并求最大流。最大流结束后，在残量网络中从 S 仍可到达的点属于左侧，其余点属于右侧；原图中从左侧跨到右侧的边组成最小割， 其容量和等于最大流。