Tag: 费用流

5 篇文章

[ZJOI2010]网络扩容
题面 给定一张有向图,每条边都有一个容量 $C$ 和一个扩容费用 $W$。这里扩容费用是指将容量扩大 $1$ 所需的费用。 求: 1、 在不扩容的情况下,$1$ 到 $N$ 的最大流; 2、 将 $1$ 到 $N$ 的最大流增加 $K$ 所需的最小扩容费用。 题目链接 思路 第一问是一个裸的最大流。 对于第二问,考虑在每条边旁边加一条边,对于边 $…
[SDOI2009]晨跑
题目描述 题目大意:给出一张点数为 $n$,边数为 $m$ 的有向图,除了点 $1$ 和点 $n$ 外每个点和每条边只能走一次,求从点 $1$ 到点 $n$ 的最小费用最大流。 题目链接 思路 这道题主要是题面难理解。 由于一个点只能经过一次,我们一个点拆分为两个点,中间连一条流量为 $1$,费用为 $0$ 的边。 注意点 $1$ 和 点 $n$ …
网络流 24 题 – 分配问题
题面 题目传送 题目描述 有 $ n $ 件工作要分配给 $ n $ 个人做。第 $ i $ 个人做第 $ j $ 件工作产生的效益为 $ c_{ij} $。试设计一个将 $ n $ 件工作分配给 $ n $ 个人做的分配方案,使产生的总效益最大。 输入格式 第 $ 1 $ 行有 $ 1 $ 个正整数 $ n $,表示有 $ n $ 件工作要分配给…
网络流 24 题 – 负载平衡问题
题面 题目传送 题目描述 $G$ 公司有 $n$ 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 $n$ 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。 输入格式 第 $1$ 行中有 $1$个正整数 $n$,表示有 $n$ 个仓库。 第 $2$ 行中有 $n$ 个正整数,表示 $n$ 个仓库的库存量。…
网络流 EK (Edmond-Karp) 算法详解 求解最大流和费用流问题
前言 问题 有 $n$ 个城市,$m$ 条单向铁路连接了这些城市。每条铁路可以售 $s_i$ 张票。现在人们要从 $S$ 城去 $T$ 城,假设他们都有足够的钱去购买车票,那么最多有多少人能到达 $T$ 城? 思路 要使 $S$ 的人到达 $T$ ,首先要找到一条从 $S$ 到 $T$ 的通路(否则就到不了 $T$ 了)。显然,这条路最多只能通过其…