二分图应用场景

一、基础判定：二分图染色法

1. 社交网络分组
   用户分为敌对两群组，若关系图可二染色则存在可行方案（如Luogu P1525 关押罪犯）。
2. 课程冲突检测
   学生选课若存在时间重叠则连边，可染色法判断能否无冲突排课。

⚔️ 二、匹配优化：匈牙利算法

1. 任务分配
   人员与任务匹配（如人员技能满足任务要求），最大化匹配数。
2. 棋盘覆盖
   M×N棋盘用1×2骨牌覆盖（黑白染色后行列二分图匹配）。

🔍 三、二分答案+二分图验证

1. 最小化最大冲突值
   （如关押罪犯）二分仇恨值阈值mid，建图（>mid的边连接囚犯）后用染色法判断能否二分图划分。
2. 资源调度优化
   服务器分配任务时延上限mid，检验任务-服务器二分图是否存在满足时延约束的匹配。

四、二分图模型扩展

1. 最小点覆盖
   监控问题（选最少的点覆盖所有边）→ König定理：最小点覆盖 = 最大匹配数。
2. 最大独立集
   互不攻击的棋子布局 → 最大独立集 = 总点数 - 最小点覆盖。

💡 信奥题型速查表

✅ 备考要点

1. 染色法模板：需熟练写出非递归BFS染色代码，注意处理非连通图。
2. 匈牙利优化：掌握邻接表存图与递归匹配实现，复杂度O(VE)。
3. 逆向思维：当直接建模困难时，尝试将边权/冲突转化为二分图判定条件。

二分图的核心价值在于 将复杂关系约束转化为两类集合的交互，掌握染色法与匈牙利算法即可解决信奥中90%的二分图题型。