[luoguP2045] 方格取数加强版（最小费用最大流）传送门
水题
——代码
1 #include <queue>
2 #include <cstdio>
3 #include <cstring>
4 #include <iostream>
5 #define N 51
6 #define M 100001
7 #d
火星探险问题此题oj上无spj，无法提交
【问题分析】
最大费用最大流问题。
【建模方法】
把网格中每个位置拆分成网络中两个节点<i.a>,<i.b>，建立附加源S汇T。
1、对于每个顶点i，j为i东边
[CODEVS1917] 深海机器人问题（最小费用最大流）传送门
【问题分析】
最大费用最大流问题。
【建模方法】
把网格中每个位置抽象成网络中一个节点，建立附加源S汇T。
1、对于每个顶点i，j为i东边或南边相邻的一个节点，连接节
[CODEVS1916] 负载平衡问题（最小费用最大流）传送门
输入所有 a[i]，求出平均值 sum，每个 a[i] = sum
那么如果 a[i] > 0，从 s 向 i 连一条容量为 a[i] 费用为 0 的有向边
如果 a[i] < 0，从 i 向 t 连一条容量为 a[i]
[CODEVS1915] 分配问题（最小费用最大流）传送门
脑残题
建图都懒得说了
——代码
1 #include <queue>
2 #include <cstdio>
3 #include <cstring>
4 #include <iostream>
5 #define N 1000001
6 #
[CODEVS1914] 运输问题（最小费用最大流）传送门
水题。
建图都不想说了
——代码
1 #include <queue>
2 #include <cstdio>
3 #include <cstring>
4 #include <iostream>
5 #define INF 1e9
6 #de
[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] 方格取数问题（最大点权独立集）传送门
引入两个概念：
最小点权覆盖集：满足每一条边的两个端点至少选一个的最小权点集。
最大点权独立集：满足每一条边的两个端点最多选一个的最大权点集。
现在对网格染色，使
[luoguP2766] 最长递增子序列问题（最大流）传送门
题解来自网络流24题：
【问题分析】
第一问时LIS，动态规划求解，第二问和第三问用网络最大流解决。
【建模方法】
首先动态规划求出F[i]，表示以第i位为开头的最长上升序
[luoguP2763] 试题库问题（最大流）传送门
每个类别和它所有的试题连一条权值为1的边。
增加一个超级源点s，s和每个类别连一条权值为选当前类别数量的边。
增加一个超级汇点t，每个试题和t连一条权值为1的边。
[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
【模板】最小费用最大流洛谷模板题
没什么好说的，用spfa来找增广路。
1 #include <cstdio>
2 #include <cstring>
3 #include <queue>
4
5 using namespace std;
6
7 const int
