网络流24题最小割=最大流
最大权闭合图=正权边之和最小割
听说这24个题很好。
开始填坑吧。
1.飞行员配对方案问题　　二分图最大匹配　　　　传送门　　（好像就是个模板呀）
2.太空飞行

[luoguP2764] 最小路径覆盖问题（最大流 || 二分图最大匹配）传送门

可惜洛谷上没有special judge，不然用匈牙利也可以过的，因为匈牙利在增广上有一个顺序问题，所以没有special judge就过不了了。
好在这个题的测试数据比较特殊，如果是网

[1143] [CTSC2008]祭祀river（最大独立集 || 偏序集最大反链）传送门

网上说这是偏序集最大反链，然而我实在不理解。
所以我换了一个思路，先用floyd，根据点的连通性连边，
问题就转换成了找出最多的点，使任意两个点之间不连边，也就是最大独立

[POJ3041] Asteroids（最小点覆盖-匈牙利算法）传送门

题意：

给一个N*N的矩阵，有些格子有障碍，要求我们消除这些障碍，问每次消除一行或一列的障碍，最少要几次。



解析：
把每一行与每一列当做二分图两边的点。


某格子有障

[POJ2446] Chessboard（二分图最大匹配-匈牙利算法）传送门

把所有非障碍的相邻格子彼此连一条边，然后求二分图最大匹配，看 tot * 2 + k 是否等于 n * m 即可。
但是连边不能重复，比如 a 格子 和 b 格子 相邻，不能 a 连 b ，b 也连

[POJ2594] Treasure Exploration（最小路径覆盖-传递闭包 + 匈牙利算法）传送门

引子：
有一个问题，是对于一个图上的所有点，用不相交的路径把他们覆盖，使得每个点有且仅属于一条路径，且这个路径数量尽量小。
对于这个问题可以把直接有边相连的两点 x

飞行员配对方案问题（匈牙利算法+sort）洛谷传送门
匈牙利算法+sort
没什么好说的。
——代码


1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4
5 using namespace std;
6
7 int

[USACO11NOV]牛的障碍Cow Steeplechase（匈牙利算法）洛谷传送门
题目描述：
给出N平行于坐标轴的线段，要你选出尽量多的线段使得这些线段两两没有交点（顶点也算），横的与横的，竖的与竖的线段之间保证没有交点，输出最多能选出多少条线段

【模板】二分图匹配洛谷模板题
学了匈牙利算法。
匈牙利算法核心是找增广路经。
可以求出二分图的最大匹配数。
感觉还是挺好理解的。
时间复杂度　　邻接矩阵：　　邻接表：
空间复杂度　　邻接