跳到主要内容

4 篇博文 含有标签「algorithm」

查看所有标签

· 13 分钟阅读
顾淇元 Alex

在今天 C 社 OI 部的活动中,我们先进行了破冰活动——自我介绍并交流有趣的算法知识。通过这独特的形式我们得以增进对彼此的了解,并为之后的合作打下基础。

之后,我们挑选了最感兴趣的网络流这一类算法问题进行详细的讲解。我们从网络流图的基本概念开始,例如源,汇点剩余容量最大流最小割 等等。其中最为趣味的是最小割,其定义为删去若干条边使得某两点 (u,v)(u,v) 不互通,这若干条边边权和的最小值。

接下来通过不断优化算法,例如灵活运用 Edmond-Karp 动能算法(复杂度 O(nm2)O(nm^2) ), Dinic 算法(复杂度 O(n2m)O(n^2m) )和 ISAP 算法(复杂度 O(n2m)O(n^2m) ,不需 BFS 多次)。此外还讲解了一个优美的定理:最大流最小割定理。这一定理在一些图论问题中有着有趣的应用:

· 7 分钟阅读
Josh Cena

这是 C 社算法团队的第五次活动。由于 12 月 USACO 竞赛在即,我们展开了针对性的练习。第一次活动我们从铜组开始练习,由于成员们水平较高,我们挑选了一道有一定编程水平要求的铜组题目。铜组题目只要求对循环的掌握,一定可以通过枚举得到结果,因此对算法和数据结构没有太高要求。

· 5 分钟阅读
DoremySwee

这是 C 社算法团队的第三次活动。我们研究了一道上海省选的题目,主要运用了状态压缩动态规划算法。其中数学部分比较困难,尚未给出严格证明。

· 3 分钟阅读
Josh Cena

这是 C 社算法团队的第一次活动。我们介绍了斐波那契数列的第nn项求解方法,主要运用了矩阵快速幂算法。