4 篇博文 含有标签「algorithm」

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

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

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

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

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

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