最小割文章列表

[luoguP2805] [NOI2009]植物大战僵尸（网络流）

传送门 结论：这是最大权闭合图的模型 因为可能A保护B，B保护A，出现环。 所以由植物A向植物A保护的植物连边，然后拓扑排序，将环去掉。 然后将拓扑排序的边反向连，建立最大权闭合图的模型。 跑最大流（...最大流,最小割,最大权闭合图

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

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

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

传送门 引入两个概念： 最小点权覆盖集：满足每一条边的两个端点至少选一个的最小权点集。 最大点权独立集：满足每一条边的两个端点最多选一个的最大权点集。 现在对网格染色，使得相邻两点颜色不同，之后把两个...最大流,网络流,最大独立集,最小点覆盖,最小割

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

传送门 如果将每一个实验和其所对的仪器连一条有向边，那么原图就是一个dag图（有向无环） 每一个点都有一个点权，实验为收益（正数），仪器为花费（负数）。 那么接下来可以引出闭合图的概念了。 闭合图是原...最大流,最小割,网络流

网络流24题

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

共1页/5条

---

香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化