Tutorial

阅读本文前应熟悉容量网络求 最大流增广路算法
具体可参考 Maximum Flow Minimum Cut 的相关内容。

Minimum Cost Maximum Flow ,即 最小费用最大流 ,又称 费用流
它指的是 带费用的 容量网络上 总花费最小 的最大流。
下面将给出前置知识并介绍求费用流的算法,附板子题。

Read More »

Tutorial

阅读本文前应熟悉 网络流基础 ,具体可参考 Network Flow .

Maximum Flow Minimum Cut ,即 最大流最小割
容量网络的 最大流最小割 是网络流问题中常见的研究对象。
两者的关系由 Max-Flow Min-Cut Theorem ,即 最大流最小割定理 指出。
求最大流的算法包括 EK , Dinic , ISAPHLPP 等。
下面将给出前置知识并分别介绍上述的 Theorem 和算法,附板子题。

Read More »

Tutorial

Maxmum Clique ,即 最大团
Maximum Independent Set ,即 最大独立集
两者的本质是相同的,它们的关系由 König Theorem 指出。
求最大团或最大独立集是 图论 中的常见问题。
下面将给出前置知识并介绍相关算法,附板子题。

Read More »

Prologue

因为期末的原因过了大半个月才补的游记 orz
去西安之前就听说两极分化严重 没错我就是蒻的那一极
尽管如此能申请到名额还是挺开心的,抱着拿块铜的想法去的 ~
可惜最后比铜末多了 3 min 罚时 QAQ
不过中间的心态比上次去上海好多了,算是有点习惯赛场了吧!

Read More »

Prologue

「就算狼狈不堪也好,跑远些,活下去。人活着比什么都好。」
森田森吾说过的话在漆黑的雨水管道中回响。
「森田,」青柳雅春喘着粗气问道,「这也是森林的声音告诉你的吗?」
才不是呢,是我自己说的。他听到了这样的回答。

伊坂幸太郎
《金色梦乡・事件》

Read More »

Tutorial

阅读本文前应熟悉 FWT 及其原理,具体可参考 Fast Walsh Transform .

Fast Möbius Transform ,即 快速莫比乌斯变换 ,简称 FMT .
FMT 一般用于加速 集合卷积运算 ,实际上完全可以用 FWT 代替。
下面将给出前置知识并介绍 FMT 及其原理。

Read More »

Tutorial

阅读本文前应熟悉 FFT 及其原理,具体可参考 Fast Fourier Transform .

Fast Walsh Transform ,即 快速沃尔什变换 ,简称 FWT .
FWT 一般用于加速关于 下标位运算 的卷积,有 OR , ANDXOR 三种形式。
下面将介绍 FWT 及其原理,附板子题。

Read More »