RainAir
My OI Blog
RainAir


文章归档

Stoer Wagner 算法

Stoer Wagner 算法主要是解决无向图最小割的问题。 题目链接 给定一张无向图,每一条边都有其花费,求最少能使这张图不连通应割掉的边数。 原作者论文,侵删 解题思路 首先我们可以使用网络流暴力跑,也就是随机一个源点然后枚举汇点跑最大流那种,但是时间复杂度…

   233   2018-12-25 去围观

「POJ1966」Cable TV Network

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

   153   2018-12-24 去围观

网络流建模总结

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

   295   2018-12-15 去围观

「BZOJ 1280」Emmy卖猪pigs

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

   100   2018-12-14 去围观

AC 自动机学习笔记

定义 首先简要介绍一下 AC 自动机:Aho-Corasick automation,该算法在 1975 年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出 n 个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂 AC 自动机,先得有模式树(…

   214   2018-12-11 去围观

Trie 树学习笔记

定义 又称单词查找树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较…

   193   2018-12-10 去围观

最小费用最大流学习笔记

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

   413   2018-12-08 去围观

密码保护:「19省选1」题解

这篇文章受密码保护,输入密码才能看哦

   234   2018-12-05 去围观

最大权闭合子图

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

   213   2018-12-03 去围观

「计算几何初步」找平面凸包

定义 对一个简单多边形来说,如果给定其边界上或内部的任意两个点,连接这两个点的线段上的所有点都被包含在该多边形的边界上或内部的话,则该多边形为凸多边形 。 一般有两种方法:Graham 扫描法和 Jarvis 步进法。但是由于作者本人姿势水平有限,这里只介绍 Graham…

   236   2018-12-02 去围观
文章归档