标签: 网络流

3 篇文章

最小费用最大流(MCMF)简要学习笔记
在打 P3705 [SDOI2017]新生舞会 时发现原代码似乎出了点问题。现在不推荐本博客的写法,更推荐类似于 Dinic 的 spfa+dfs 的写法,详见最下方的“附加代码”部分。 MCMF(基于 spfa 实现) 模板题:Luogu3381。 即给定一张网络,每条边都有一个权值和流量限度,这条边上每有一个流量,总费用就加上这个权值,你需要在…
网络最大流学习笔记——Dinic
博客参考:学委 的 博客 及 代码启示 暴力最大流 模板题:Luogu3376 在学习 Dinic 之前,必须先要知道暴力最大流的写法。 首先理解何为网络最大流。一张网络就是一张带权有向图,源点可以输出无限的流量,但是每一条边都有一个容量,需要满足这条边上的流量不能超出其容量(可以理解为输水系统),最后所有流量都会被汇点接收。我们需要求出这个网络运…
P2065 [TJOI2011]卡片 题解
题目链接 题意 给定一个二分图,二分图上的每个点都有一个权值。如果一个左部点的权值和一个右部点的权值的 $\gcd$ 大于 $1$,则这两点之间有一条边。求二分图最大匹配。 解析 首先我们发现,如果暴力建边的话,我们可能会建 $n^2$ 条边,在 $100$ 组数据的情况下,非常容易 TLE。 我们考虑优化。对于一个左部点的权值和一个右部点的权值的…