4 posts tagged with "algorithm"

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

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

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

This is the fifth activity of Computerization algorithm team. Because the December USACO contest is almost there, we had some targeted practicing, starting with Bronze problems. Because members already have decent understanding, we chose a tough one. Bronze division problems only require mastery of loops, so a brute-force enumaration will always work, with no requirement of algorithms or data structures.

This is the first activity of Computerization algorithm team. We discussed a problem from Shanghai NOI regional selection, which leverages state compression dynamic programming. The mathematics is beyond our capacity to be rigorously proven.

This is the first activity of Computerization algorithm team. We introduced the method to find the $n$th term of the Fibonacci sequence, which mainly uses matrix exponentiation.