最小割模型

发布于 18 天前

网络流题目中,如果一种物品有两种状态(选或不选),告诉你每一种状态产生的收益/代价,我们就可以通过使用最小割模型来解决这个问题。但 …


「POJ1966」Cable TV Network

发布于 2018-12-24

题目链接 题目描述 给定一张无向图,求让这张无向图不连通应删去的点的最小个数。 解题报告 首先发现这很像割的定义,只不过由边转化为 …


网络流建模总结

发布于 2018-12-15

输出方案 回忆前面我们解决二分图的方法:源点向每个左端节点连一个容量为 $1$ 的弧,每个右侧端点向汇点连一个容量为 $1$ 的弧 …


「BZOJ 1280」Emmy卖猪pigs

发布于 2018-12-14

题目链接 题目描述 Emmy 在一个养猪场工作。这个养猪场有M个锁着的猪圈,但 Emmy 并没有钥匙。顾客会到养猪场来买猪,一个接 …


最小费用最大流学习笔记

发布于 2018-12-08

最小费用最大流 定义 我想你一定学会了最大流算法。 模板题链接 我们发现在同一个网络中,可能会有多个总流量相同的最大流 $f$,我 …


最大权闭合子图

发布于 2018-12-03

题目链接 模型描述 有一个工厂,接到了 $n$ 个订单,为了完成这些订单,工厂需要采购一些机器,一共可采购 $m$ 台机器。我们知 …