Stoer Wagner 算法

发布于 2018-12-25

Stoer Wagner 算法主要是解决无向图最小割的问题。 题目链接 给定一张无向图,每一条边都有其花费,求最少能使这张图不连通 …


「POJ1966」Cable TV Network

发布于 2018-12-24

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


网络流建模总结

发布于 2018-12-15

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


「BZOJ 1280」Emmy卖猪pigs

发布于 2018-12-14

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


AC 自动机学习笔记

发布于 2018-12-11

定义 首先简要介绍一下 AC 自动机:Aho-Corasick automation,该算法在 1975 年产生于贝尔实验室,是著 …


Trie 树学习笔记

发布于 2018-12-10

定义 又称单词查找树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串), …


最小费用最大流学习笔记

发布于 2018-12-08

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


最大权闭合子图

发布于 2018-12-03

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


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

发布于 2018-12-02

定义 对一个简单多边形来说,如果给定其边界上或内部的任意两个点,连接这两个点的线段上的所有点都被包含在该多边形的边界上或内部的话, …