最大流文章列表
[luoguP2805] [NOI2009]植物大战僵尸（网络流）
传送门 结论：这是最大权闭合图的模型 因为可能A保护B，B保护A，出现环。 所以由植物A向植物A保护的植物连边，然后拓扑排序，将环去掉。 然后将拓扑排序的边反向连，建立最大权闭合图的模型。 跑最大流（...最大流,最小割,最大权闭合图
[luoguP2754] 星际转移问题（最大流）
传送门 不同的时间每个飞船所在的地点不同，给我们启示按照时间构建分层图。 同一个地点 x x, day i 1 x, day i 连一条容量为 INF 的边，因为人们可以在一个地点等待 艘飞船的路径 ...网络流,最大流
[luoguP3355] 骑士共存问题（二分图最大独立集）
传送门 模型 二分图最大独立集，转化为二分图最大匹配，从而用最大流解决。 实现 首先把棋盘黑白染色，使相邻格子颜色不同。 把所有可用的黑色格子看做二分图X集合中顶点，可用的白色格子看做Y集合顶点。 建...网络流,最大流,最小割,最大独立集
[luoguP1251] 餐巾计划问题（费用流）
传送门 模型 网络优化问题，用最小费用最大流解决。 实现 把每天分为二分图两个集合中的顶点Xi,Yi，建立附加源S汇T。 1、从S向每个Xi连一条容量为ri，费用为0的有向边。 2、从每个Yi向T连一...网络流,最大流,最小费用最大流
[cogs729]圆桌问题（最大流）
传送门 模型 二分图多重匹配问题，可以用最大流解决。 实现 建立二分图，每个单位为X集合中的顶点，每个餐桌为Y集合中的顶点，增设附加源S和汇T。 1、从S向每个Xi顶点连接一条容量为该单位人数的有向边...网络流,最大流
[luoguP2770] 航空路线问题（最小费用最大流）
传送门 模型 求最长两条不相交路径，用最大费用最大流解决。 实现 为了限制经过次数,将每个点i拆成xi,yi. 1、从xi向yi连一条容量为1,费用为1的有向边(1iN), 2、从x1向y1连一条容量...最大流,网络流,最小费用最大流
[luoguP2774] 方格取数问题（最大点权独立集）
传送门 引入两个概念： 最小点权覆盖集：满足每一条边的两个端点至少选一个的最小权点集。 最大点权独立集：满足每一条边的两个端点最多选一个的最大权点集。 现在对网格染色，使得相邻两点颜色不同，之后把两个...最大流,网络流,最大独立集,最小点覆盖,最小割
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化