文章目录
-
- 前言
- 四、二分图及图匹配
-
- 二分图常见模型
- 二分图例题
-
-
- e g 1 : eg1: eg1: [ Z J O I 2009 ZJOI2009 ZJOI2009\][假期的宿舍](https://ac.nowcoder.com/acm/contest/34649/B)(二分图最大匹配板题)
- e g 2 : eg2: eg2: [C-Going Home](https://ac.nowcoder.com/acm/contest/34649/C)（二分图带权匹配KM算法）
- e g 3 : eg3: eg3: [棋盘覆盖](https://ac.nowcoder.com/acm/contest/34649/F)（蓝书例题）
- e g 4 : eg4: eg4: [L-城市物流](https://ac.nowcoder.com/acm/contest/34649/L)（cf上也有对应原题，CF981F rating 2500，二分图匹配模型综合题）
-
- 一般图匹配
- 练习题
前言
由于图论学习总结内容过多，全放在一篇博客过于冗长现进行拆分，本文是二分图及图匹配部分，其他部分地址见：图论学习总结(For XCPC)
四、二分图及图匹配
二分图常见模型
- 二分图判定
- 黑白染色，不含奇圈（点可以分成左右两部份，每一部份内没有边）
- 最大匹配
- 增广路算法（匈牙利算法）
- 最小点覆盖
- 最大独立集
- 最小路径覆盖
- 带权匹配
- KM算法
- 二分图与网络流的联系
二分图例题
e g 1 : eg1: eg1: [ Z J O I 2009 ZJOI2009 ZJOI2009]假期的宿舍(二分图最大匹配板题)
题目大意
e g 2 : eg2: eg2: C-Going Home（二分图带权匹配KM算法）
题目大意
e g 3 : eg3: eg3: 棋盘覆盖（蓝书例题）
题目大意
给定一个 N N N行 N N N列的棋盘，已知某些格子禁止放置。求最多能往棋盘上放多少块的长度为 2 2 2、宽度为 1 1 1 的骨牌。骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。 N , M ≤ 100 N,M≤100 N,M≤100。
e g 4 : eg4: eg4: L-城市物流（cf上也有对应原题，CF981F rating 2500，二分图匹配模型综合题）
题目大意
一般图匹配
练习题
A-情侣和聚餐(cf上也有对应题目，2600， 二分图+构造)
D-炸弹（二分图最大匹配）
[E-ZJOI2007]矩阵游戏（二分图最大匹配）
H-占领城市(最小路径覆盖，拆点跑最大匹配或最大流)
I-中心图（思维+暴力+二分图匹配）
J-插座（思维+暴力+二分图匹配，2017-2018 ACM-ICPC German Collegiate Programming Contest G C P C GCPC GCPC 2017 F]）
