泪痕@一语成谶
辗转当作浮生妖,流离惊似尘世鬼
Prufer 序列 Prufer 序列
摘要 本文翻译自 e-maxx Prufer Code,兹瓷一下OI-WIKI的计划。另外解释一下,原文的结点是从 0 开始标号的,本文我按照大多数人的习惯改成了从 1 标号。 这篇文章介绍 Prufer 序列 (Prufer code)
2019.07.07
最短路应用 最短路应用
摘要 本文接上文 最短路算法,为大家介绍最短路的常见应用。 将原来打的各种题目的零散文章汇总,编入精选文章。 负环与差分约束一个看起来不像最短路的最短路应用。给出一组差分约束,问是否有解。差分约束是形容
2019.06.15
最小割树 最小割树
摘要 最近发现的一个小 Tip 任意两点最小割 对于一个网络图,我们要求任意两点间的最小割 考虑在网络图 的一个最大流 . 这显然也是 $s\right
2019.05.07
网络流入门之费用流 网络流入门之费用流
摘要 之前写的《网络流初步》内容太多,因此单独分一个费用流出来。本文的内容可能涉及到《网络流入门之最大流》的内容,建议先食用后者。 2019.6.15 编入精选文章 费用流给定一个网络 ,每条边除了有容量限制 $c(u,
2019.05.03
圆桌问题 圆桌问题
摘要 复习 Dinic~ 假设有来自 m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri (i =1,2,……,m)。 会议餐厅共有 n 张餐桌,每张餐桌可容纳 ci (i =1,2,……,n) 个代表就餐。 为了使代表
2019.04.11
[LuoguP1251] 餐巾计划问题 [LuoguP1251] 餐巾计划问题
摘要 复习一下网络流 一个餐厅在相继的 天里,每天需用一些餐巾。第 天需要 块餐巾 。餐厅可以购买新的餐巾, 每块餐巾的费用为 ;或者把旧餐巾送到快洗部,洗一块需
2019.04.06
点分治入门 点分治入门
摘要 莫名其妙发现这几天遇到了很多点分治的题目,于是来系统整理一下点分治算法 点分治是一种树上分治算法。通常用于解决无根树上的统计问题。对于统计的问题,可以按照结点对其分类,分别统计后再组合成结果。而这类问题的求解复杂度往往和树的深度、大小
2019.03.07
网络流建模 网络流建模
摘要 网络流算法本身不难,但是很多情况下难以被想到。其原因就在于网络流模型过于抽象,与表面的题目关联性不强。本文就从常见的建模角度,浅谈网络流建模 最大流建模魔术球问题 有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1,
2019.03.02
生成树算法 生成树算法
补一篇生成树(Spanning Tree)的文章 生成树一个比较鬼扯的定义:对于一个图 ,它的生成树是一个连通子图 ,其中 。 最小生成树对于一个加权图 G,最小生成树(M
2019.01.17
[NOI2009] 变换序列 [NOI2009] 变换序列
题意在 的整数序列中,定义两个数 的距离为 . 现要求构造一个序列 ,使得每一个
2019.01.15
[SCOI2010] 连续攻击游戏 [SCOI2010] 连续攻击游戏
题意游戏里有很多的装备,每种装备都有 2 个属性,属性值为 [1,10000] 之间的数。 使用某种装备只能使用该装备的一个属性。每种装备最多只能使用一次。 要求使用的装备的属性值从 1 开始连续递增,想知道他最多能连续攻击多少次? 分析
2019.01.14
[ZJOI2010] 网络扩容 [ZJOI2010] 网络扩容
题意给定一张有向图,每条边都有容量 和扩容费用 。这里扩容费用指将容量扩大 1 所需的费用。求: 在不扩容的情况下,1 到 N 的最大流. 将 1 到 N 的最大流增加 K 所需的最小扩容费用. Subtask1
2019.01.14
[CQOI2012] 交换棋子 [CQOI2012] 交换棋子
题意有一个 n 行 m 列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第 i 行第 j 列的格子只能参与 次交换。 求最小交换总次数。如果无解,输出 -1。 分析非
2019.01.14
[SDOI2009] 晨跑 [SDOI2009] 晨跑
题意在加权有向图中求一路径集合 满足 起点为 ,终点为 ,即 . 集合内的路径除了起点终
2019.01.12
[LuoguP2764] 最小路径覆盖问题 [LuoguP2764] 最小路径覆盖问题
DAG 的最小路径点覆盖给定有向图 。设 的一个简单路(顶点不相交的路)的集合。 如果 中每个顶点恰好在 的一条路上,则称 的一个路径覆盖。 中路径可以从 $V
2019.01.05
网络流入门之最大流 网络流入门之最大流
摘要 网络流是强有力的图论算法之一,其算法本身不难,但是所解决的问题却千变万化。简而言之,网络流的难点在于建模。本文则注重讲解网络流的最大流算法。 2019.6.14:收编精选文章。 网络网络是指一个有向图 . 每条边
2018.12.21
二分图漫谈 二分图漫谈
二分图一个无向连通图 中存在 满足 $\forall x,y\in B
2018.12.21
[LuoguP2756] 飞行员配对方案问题 [LuoguP2756] 飞行员配对方案问题
分析二分图匹配,直接网络流模板 输出方案的时候,判断每条边是否图上剩余容量为 0 的边即可 代码#include<cstdio> #include<cstring> #include<queue> using namesp
2018.12.21
[LuoguP3386] 二分图匹配 [LuoguP3386] 二分图匹配
分析网络流算法,左部右部分别连源点汇点,置容量为 1,跑一遍 dinic 或者 EK 即可 代码#include<cstdio> #include<cstring> #include<queue> using namesp
2018.12.21
Tarjan 之有向图 SCC Tarjan 之有向图 SCC
tarjan 一直是我认为非常玄学的算法。首先不提它的描述之模糊,dalao 们写的博客之雷同。这算法的应用就很玄学。于是,本蒟蒻今天就来揭开它神秘的面纱…… Tarjan 与 DFS 生成树Tarjan 算法是由 Robert Tarja
2018.12.06
1 / 2