SkyWT

Welcome!

之前已经介绍过,网络流中最大流就是满足网络流的三个限制前提下,源点到汇点的最大流量,可以用 Edmonds-Karp 算法或者 Dinic 算法求解。
网络流的一个割,定义为对所有点集的一个二划分(就是划分为两个点集),使得源点和汇点处于不同的点集中。假设源点 s 在点集 S 中,汇点 t 在点集 T 中,割集就是这两个点集中的点分别连的边,也就是 (u,v),u\in S,v \in T。最小割就是使割集内边权和最小的割集。
下面我们要证明一个结论:网络流的最小割容量=最大流量。

Read more...

发布 0 条评论

据说很多公司都有这样一道面试题:给你几个 G 的字符串,让你想办法快速地找出其中的很多个需要和谐的敏感词。
这个问题里,如果“需要和谐的字符串”称为“模式串”,“待被查的字符串”称为文本串。对于这样的问题,如果暴力做,复杂度就是 \Theta(N \ast M \ast Len)……用 AC 自动机这种高级的算法,可以在 \Theta (N) 左右复杂度内得出答案。Excited!

Read more...

发布 0 条评论

在一幅无向图中,如果删除了一个点,导致图分成了两个或多个联通块(强连通分量),那么这个点就是割点。怎么求这样的点呢?最原始暴力的方法就是每次枚举一个点,删除,跑一遍最短路。今天我们可以用更高级的 Tarjan 算法 \displaystyle \Theta (N) 求解。

Read more...

发布 0 条评论