Wilson's blog: 博客!

算法

Dinic算法

本文讲解Dinic算法的思路，算法本身与证明。

关于残余网络和增广路等概念的说明，请看Ford-Fulkerson算法这篇文章。这里只致力于改进Ford-Fulkerson算法，得到一个与 $$F$$ 无关的算法。

网络流

最大流问题

举个例子，互联网上有几台计算机，某些计算机之间建立了一定带宽的有向连接。目标是将数据从某台指定的计算机 $$s$$ （称为源点）传输到 $$t$$ （称为汇点），求单位时间内最多能传输多少数据。

有许多类似的问题，都可以抽象成类似的网络流问题，上面的问题是一个（单源单汇）最大流问题。

算法

Ford-Fulkerson算法

本文讲解Ford-Fulkerson算法的思路，算法本身与证明，最后会给出模板。Ford-Fulkerson算法是增广路算法的一种，用于求解最大流问题，不明背景请看网络流这篇文章。

题解

POJ2987-Firing

这是一道最大点权闭合图的问题，有论文最小割模型在信息学竞赛中的应用（%%）。这类问题的解法是建图转化成最小割问题，再用最大流求解。

Code Highlight Style test

Make sure all the code blocks highlighted correctly. All the code samples are come from the demo of https://highlightjs.org

Markdown Style test

This post is originated from here and is used for testing markdown style. This post contains nearly every markdown usage. Make sure all the markdown elements below show up correctly.

Images

This is a image test post.

Caption

Small Picture

This post doesn’t have a title. Make sure it’s accessible.

Excerpts

The following contents should be invisible in home/archive page.

Videos

This is a video test post.

Youtube

Vimeo