网络流文章列表
[luoguP2770] 航空路线问题（最小费用最大流）
传送门 模型 求最长两条不相交路径，用最大费用最大流解决。 实现 为了限制经过次数,将每个点i拆成xi,yi. 1、从xi向yi连一条容量为1,费用为1的有向边(1iN), 2、从x1向y1连一条容量...最大流,网络流,最小费用最大流
[luoguP2774] 方格取数问题（最大点权独立集）
传送门 引入两个概念： 最小点权覆盖集：满足每一条边的两个端点至少选一个的最小权点集。 最大点权独立集：满足每一条边的两个端点最多选一个的最大权点集。 现在对网格染色，使得相邻两点颜色不同，之后把两个...最大流,网络流,最大独立集,最小点覆盖,最小割
[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...网络流,匈牙利算法,二分图,最大流,最大权完美匹配
飞行员配对方案问题（匈牙利算法+sort）
洛谷传送门 匈牙利算法+sort 没什么好说的。 ——代码 1 #include cstdio 2 #include cstring 3 #include algorithm 4 5 using na...二分图,匈牙利算法,stl,最大匹配,网络流
【模板】最小费用最大流
洛谷模板题 没什么好说的，用spfa来找增广路。 1 #include cstdio 2 #include cstring 3 #include queue 4 5 using namespace s...最小费用最大流,最大流,堆,模板,stl
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化