RainAir
My OI Blog
RainAir

网络流
文章归档

最小割模型

网络流题目中,如果一种物品有两种状态(选或不选),告诉你每一种状态产生的收益/代价,我们就可以通过使用最小割模型来解决这个问题。但是如果物品的状态扩展到了 $k$ 种,我们就需要用一种新的建图方法。 我们拿两道题目举例: RatingProgressAward *TCO2017 Semi…

   182   2019-08-01   182 去吊打作者

「POJ1966」Cable TV Network

题目链接 题目描述 给定一张无向图,求让这张无向图不连通应删去的点的最小个数。 解题报告 首先发现这很像割的定义,只不过由边转化为了点。 那我们不妨拆点来对边进行限制:其中对于每个点 $v$ 拆成 $v$ 和 $v'$ ,然后我们在这两个点之间连一条容量为 $1$ 的边…

   327   2018-12-24   327 去吊打作者

网络流建模总结

输出方案 回忆前面我们解决二分图的方法:源点向每个左端节点连一个容量为 $1$ 的弧,每个右侧端点向汇点连一个容量为 $1$ 的弧,原图中的边容量为 $1$;所以说如果我们想获取方案的话我们只需要遍历左端点相连的弧是否满流即可。 交叉分组 建图方法显然,每个班级…

   528   2018-12-15   528 去吊打作者

「BZOJ 1280」Emmy卖猪pigs

题目链接 题目描述 Emmy 在一个养猪场工作。这个养猪场有M个锁着的猪圈,但 Emmy 并没有钥匙。顾客会到养猪场来买猪,一个接着一个。每一位顾客都会有一些猪圈的钥匙,他们会将这些猪圈打开并买走固定数目的猪。 所有顾客有的钥匙和他们需要买猪的数量在事先都告诉了…

   328   2018-12-14   328 去吊打作者

最小费用最大流学习笔记

最小费用最大流 定义 我想你一定学会了最大流算法。 模板题链接 我们发现在同一个网络中,可能会有多个总流量相同的最大流 $f$,我们可以在计算流量的基础上,给网络中的弧增加一个单位流量的费用(简称费用),在确保流量最大的前提下总费用最小,这样的最大流叫做…

   690   2018-12-08   690 去吊打作者

最大权闭合子图

题目链接 模型描述 有一个工厂,接到了 $n$ 个订单,为了完成这些订单,工厂需要采购一些机器,一共可采购 $m$ 台机器。我们知道完成每个订单的收益,也知道购买某个机器的开销。一个订单需要对应地购买某些机器,一台机器可以同时完成多个订单。现在工厂决定选择…

   585   2018-12-03   585 去吊打作者

Dinic 学习笔记

Dinic 是一种网络最大流的算法。 引入 网络流的本质是线性规划。 定义:有向图 $(V,E)$ 存在源点 $S \in V$ 和汇点 $T \in V,S \neq T$,每条边都有一个容量 $c$。 对于任意一个时刻,设 $flow(u,v)$ 表示实际流量,则整个图 $G$ 的流网络满足如下性质: 1. 容量限…

   524   2018-11-22   524 去吊打作者
标签
近期评论