最大流文章列表
[luoguP2763] 试题库问题（最大流）
传送门 每个类别和它所有的试题连一条权值为1的边。 增加一个超级源点s，s和每个类别连一条权值为选当前类别数量的边。 增加一个超级汇点t，每个试题和t连一条权值为1的边。 求最大流即可。 ——代码 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就过不了了。 好在这个题的测试数据比较特殊，如果是网络流的...匈牙利算法,最大流,网络流,最大匹配,最小路径覆盖
[luoguP2762] 太空飞行计划问题（最大权闭合图—最小割—最大流）
传送门 如果将每一个实验和其所对的仪器连一条有向边，那么原图就是一个dag图（有向无环） 每一个点都有一个点权，实验为收益（正数），仪器为花费（负数）。 那么接下来可以引出闭合图的概念了。 闭合图是原...最大流,最小割,网络流
网络流24题
最小割=最大流 最大权闭合图=正权边之和最小割 听说这24个题很好。 开始填坑吧。 1.飞行员配对方案问题 二分图最大匹配 传送门 （好像就是个模板呀） 2.太空飞行计划问题 最大权闭合图 传送门 3...网络流,匈牙利算法,二分图,最大流,最大权完美匹配
【模板】网络最大流
——果断附isap代码 1 #include cstdio 2 #include cstring 3 #include iostream 4 5 using std::min; 6 7 const i...模板,最大流
飞行员配对方案问题（匈牙利算法+sort）
洛谷传送门 匈牙利算法+sort 没什么好说的。 ——代码 1 #include cstdio 2 #include cstring 3 #include algorithm 4 5 using na...二分图,匈牙利算法,stl,最大匹配,网络流
【模板】二分图匹配
洛谷模板题 学了匈牙利算法。 匈牙利算法核心是找增广路经。 可以求出二分图的最大匹配数。 感觉还是挺好理解的。 时间复杂度 邻接矩阵： 邻接表： 空间复杂度 邻接矩阵： 邻接表： 看的这个 blog ...二分图,模板,最大流,匈牙利算法,最大匹配
【模板】最小费用最大流
洛谷模板题 没什么好说的，用spfa来找增广路。 1 #include cstdio 2 #include cstring 3 #include queue 4 5 using namespace s...最小费用最大流,最大流,堆,模板,stl
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化