[luoguP2526] [SHOI2001]小狗散步（二分图最大匹配）传送门简直就是模板题啊！#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#define N 101using namespace std;int n, m, cnt;int X1[N], Y1[N], X2[
[luoguP3231] [HNOI2013]消毒（最小点覆盖 + 状压）传送门考虑贪心，控制某一维为1，另两位最大是最优的，也就是一次选一个厚度为1的面那么对于每个点，可以有3种面是可以选到它的然后gg考虑二维的状态，一个平面，有些点，一次选一行或一
[luoguP1963] [NOI2009]变换序列（二分图最大匹配）传送门根据公式xjb推一下，然后就可以连边。考虑到字典序最小，和匈牙利算法的实现过程，要倒序匹配。#include <cmath>#include <cstdio>#include <vector>#include <cstring>#in
[luoguP1129] [ZJOI2007]矩阵游戏（二分图最大匹配）传送门每一行的1和每一列的1不管怎么换还是在同一行和同一列目标状态中有n个1是不同行且不同列的那么就是能否找出n个不同行不同列的1就是每一行选一个不同列的1如果矩阵中
[luoguP1640] [SCOI2010]连续攻击游戏（二分图最大匹配）传送门我们将每一个属性和物品连边，然后枚举从小到大属性跑匈牙利，直到找不到连边#include <cstdio>#include <cstring>#include <iostream>#define N 1000001#define M 20000
网络流24题最小割=最大流
最大权闭合图=正权边之和最小割
听说这24个题很好。
开始填坑吧。
1.飞行员配对方案问题 二分图最大匹配 传送门 （好像就是个模板呀）
2.太空飞行
[luoguP2764] 最小路径覆盖问题（最大流 || 二分图最大匹配）传送门
可惜洛谷上没有special judge，不然用匈牙利也可以过的，因为匈牙利在增广上有一个顺序问题，所以没有special judge就过不了了。
好在这个题的测试数据比较特殊，如果是网
[1143] [CTSC2008]祭祀river（最大独立集 || 偏序集最大反链）传送门
网上说这是偏序集最大反链，然而我实在不理解。
所以我换了一个思路，先用floyd，根据点的连通性连边，
问题就转换成了找出最多的点，使任意两个点之间不连边，也就是最大独立
[POJ3041] Asteroids（最小点覆盖-匈牙利算法）传送门
题意：
给一个N*N的矩阵，有些格子有障碍，要求我们消除这些障碍，问每次消除一行或一列的障碍，最少要几次。
解析：
把每一行与每一列当做二分图两边的点。
某格子有障
[POJ2594] Treasure Exploration（最小路径覆盖-传递闭包 + 匈牙利算法）传送门
引子：
有一个问题，是对于一个图上的所有点，用不相交的路径把他们覆盖，使得每个点有且仅属于一条路径，且这个路径数量尽量小。
对于这个问题可以把直接有边相连的两点 x
[POJ2446] Chessboard（二分图最大匹配-匈牙利算法）传送门
把所有非障碍的相邻格子彼此连一条边，然后求二分图最大匹配，看 tot * 2 + k 是否等于 n * m 即可。
但是连边不能重复，比如 a 格子 和 b 格子 相邻，不能 a 连 b ，b 也连
运动员最佳匹配问题（km算法）洛谷传送门
带权二分图最大权完美匹配。
裸的km算法。
注意开long long。
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4
5 using namespace
【模板】二分图最大权完美匹配KM算法hdu2255模板题
KM是什么意思，详见百度百科。
总之知道它可以求二分图最大权完美匹配就可以了，时间复杂度为O(n^3)。
给张图。
二分图有了边权，求最大匹配下的最大权值。
所以
飞行员配对方案问题（匈牙利算法+sort）洛谷传送门
匈牙利算法+sort
没什么好说的。
——代码
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4
5 using namespace std;
6
7 int
【转】二分图的一大坨定理转自：cnblogs/zarth/p/6417088
一、二分图最大匹配
定义：匹配是图中一些边的集合，且集合中任意两条边都没有公共点，所有的匹配中，边数最多的就是最大匹配。
算法：用匈牙利
[USACO11NOV]牛的障碍Cow Steeplechase（匈牙利算法）洛谷传送门
题目描述：
给出N平行于坐标轴的线段，要你选出尽量多的线段使得这些线段两两没有交点（顶点也算），横的与横的，竖的与竖的线段之间保证没有交点，输出最多能选出多少条线段
【模板】判断二分图给你一个无向图， 让你判断这是不是一个二分图。
二分图的标准：可以把这个图的点分成两堆，试每条边都连接这两个堆里的点，而一个堆里的点不能相连。
无向图G为二分图的充分必要
Divide Groups（分组）（二分图染色）题目链接
题目大意是说输入数字n
然后告诉你第i个人都认识谁？
让你把这些人分成两堆，使这每个堆里的人都互相认识。
做法：把不是互相认识的人建立一条边，则构建二分图，两堆的人
【模板】二分图匹配洛谷模板题
学了匈牙利算法。
匈牙利算法核心是找增广路经。
可以求出二分图的最大匹配数。
感觉还是挺好理解的。
时间复杂度 邻接矩阵： 邻接表：
空间复杂度 邻接
