题面 给定一张有向图，每条边都有一个容量 $C$ 和一个扩容费用 $W$。这里扩容费用是指将容量扩大 $1$ 所需的费用。 求： 1、 在不扩容的情况下，$1$ 到 $N$ 的最大流； 2、 将 $1$ 到 $N$ 的最大流增加 $K$ 所需的最小扩容费用。 题目链接 思路 第一问是一个裸的最大流。 对于第二问，考虑在每条边旁边加一条边，对于边 $…

题目描述 题目大意：给出一张点数为 $n$，边数为 $m$ 的有向图，除了点 $1$ 和点 $n$ 外每个点和每条边只能走一次，求从点 $1$ 到点 $n$ 的最小费用最大流。 题目链接 思路 这道题主要是题面难理解。 由于一个点只能经过一次，我们一个点拆分为两个点，中间连一条流量为 $1$，费用为 $0$ 的边。 注意点 $1$ 和 点 $n$ …

题面 题目传送 题目描述 有 $ n $ 件工作要分配给 $ n $ 个人做。第 $ i $ 个人做第 $ j $ 件工作产生的效益为 $ c_{ij} $。试设计一个将 $ n $ 件工作分配给 $ n $ 个人做的分配方案，使产生的总效益最大。 输入格式 第 $ 1 $ 行有 $ 1 $ 个正整数 $ n $，表示有 $ n $ 件工作要分配给…

题面 题目传送 题目描述 $G$ 公司有 $n$ 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 $n$ 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。 输入格式 第 $1$ 行中有 $1$个正整数 $n$，表示有 $n$ 个仓库。 第 $2$ 行中有 $n$ 个正整数，表示 $n$ 个仓库的库存量。…

前言 问题 有 $n$ 个城市，$m$ 条单向铁路连接了这些城市。每条铁路可以售 $s_i$ 张票。现在人们要从 $S$ 城去 $T$ 城，假设他们都有足够的钱去购买车票，那么最多有多少人能到达 $T$ 城？ 思路 要使 $S$ 的人到达 $T$ ，首先要找到一条从 $S$ 到 $T$ 的通路（否则就到不了 $T$ 了）。显然，这条路最多只能通过其…