题面 给定一张有向图，每条边都有一个容量 $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$ 个仓库的库存量。…

题面 洛谷 P2774 题目描述 在一个有 $m*n$ 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 $2$ 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。 输入格式 第 1 行有 2 个正整数 $m$ 和 $n$，分别表示棋盘的行数和列数。接下…

题面 描述 洛谷 P2598 狼爱上羊啊爱的疯狂，谁让他们真爱了一场； 狼爱上羊啊并不荒唐，他们说有爱就有方向…… Orez 听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez 的羊狼圈可以看作一个 n*m 个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是 Drake 很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只…

题面 洛谷 P2763 & LOJ #6006 题目描述 假设一个试题库中有 $ n $ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $ m $ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 输入格式 第 $ 1 $ 行有 $ 2 $ 个正整数 $ k $ 和 $ n $。$…

题面 在一个 r 行 c 列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为 1，蜥蜴的跳跃距离是 d，即蜥蜴可以跳到平面距离不超过 d 的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减 1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度…

题面 题目传送 给定有向图 $G=(V,E)$ 。设 $P$ 是 $G$ 的一个简单路(顶点不相交)的集合。如果 $V$ 中每个定点恰好在$P$的一条路上，则称 $P$ 是 $G$ 的一个路径覆盖。$P$中路径可以从 $V$ 的任何一个定点开始，长度也是任意的，特别地，可以为 $0$ 。$G$ 的最小路径覆盖是 $G$ 所含路径条数最少的路径覆盖。…

题面 洛谷 P2756 飞行员配对方案问题 LOJ #6000.「网络流 24 题」搭配飞行员 因为 LOJ 上的版本比较简洁，所以就放这个版本的题面了。 飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员，需一个正驾驶员（英国）和一个副驾驶员（外籍）。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞…