[luoguP2805] [NOI2009]植物大战僵尸（网络流）传送门结论：这是最大权闭合图的模型因为可能A保护B，B保护A，出现环。所以由植物A向植物A保护的植物连边，然后拓扑排序，将环去掉。然后将拓扑排序的边反向连，建立最大权闭合图的模型

[luoguP2754] 星际转移问题（最大流）传送门

不同的时间每个飞船所在的地点不同，给我们启示按照时间构建分层图。
同一个地点 x <x, dayi 1>> <x, dayi>连一条容量为 INF 的边，因为人们可以在一个地点等待
艘飞

[luoguP3355] 骑士共存问题（二分图最大独立集）传送门

模型
二分图最大独立集，转化为二分图最大匹配，从而用最大流解决。
实现
首先把棋盘黑白染色，使相邻格子颜色不同。
把所有可用的黑色格子看做二分图X集合中顶点，可用的

[luoguP2762] 太空飞行计划问题（最大权闭合图—最小割—最大流）传送门

如果将每一个实验和其所对的仪器连一条有向边，那么原图就是一个dag图（有向无环）
每一个点都有一个点权，实验为收益（正数），仪器为花费（负数）。
那么接下来可以引出闭合图的概

[luoguP1251] 餐巾计划问题（费用流）传送门

模型
网络优化问题，用最小费用最大流解决。

实现
把每天分为二分图两个集合中的顶点Xi,Yi，建立附加源S汇T。
1、从S向每个Xi连一条容量为ri，费用为0的有向边。
2、从

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

[cogs729]圆桌问题（最大流）传送门

模型
二分图多重匹配问题，可以用最大流解决。
实现
建立二分图，每个单位为X集合中的顶点，每个餐桌为Y集合中的顶点，增设附加源S和汇T。
1、从S向每个Xi顶点连接一条容

[luoguP2770] 航空路线问题（最小费用最大流）传送门

模型
求最长两条不相交路径，用最大费用最大流解决。
实现
为了限制经过次数,将每个点i拆成xi,yi.
1、从xi向yi连一条容量为1,费用为1的有向边(1<i<N),
2、从x1向y1

[luoguP2774] 方格取数问题（最大点权独立集）传送门

引入两个概念：
最小点权覆盖集：满足每一条边的两个端点至少选一个的最小权点集。
最大点权独立集：满足每一条边的两个端点最多选一个的最大权点集。
现在对网格染色，使

[luoguP2763] 试题库问题（最大流）传送门

每个类别和它所有的试题连一条权值为1的边。
增加一个超级源点s，s和每个类别连一条权值为选当前类别数量的边。
增加一个超级汇点t，每个试题和t连一条权值为1的边。

[luoguP2766] 最长递增子序列问题（最大流）传送门

题解来自网络流24题：
【问题分析】
第一问时LIS，动态规划求解，第二问和第三问用网络最大流解决。
【建模方法】
首先动态规划求出F[i]，表示以第i位为开头的最长上升序

[luoguP2765] 魔术球问题（最大流—最小不相交路径覆盖）传送门

枚举球的个数 num
如果 i < j && (i + j) 是完全平方数，那么 i > j' 连一条边
再加一个超级源点 s，s > i
再加一个超级汇点 t，i' > t
那么当前可以放的柱子的最小数量

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

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

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


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

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

【模板】网络最大流——果断附isap代码


1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4
5 using std::min;
6
7 const int maxn = 200001;
8
9 int n, m,

【模板】最小费用最大流洛谷模板题
没什么好说的，用spfa来找增广路。


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