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

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

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

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

题面 题目描述 小A有一个 $1-2^N$ 的排列 $A[1..2^N]$ ,他希望将 $A$ 数组从小到大排序, 小$A$可以执行的操作有 $N$ 种,每种操作最多可以执行一次,对于所有的 $i(1<=i<=N)$，第i中操作为将序列从左到右划分为 $2^{N-i+1}$ 段,每段恰好包括 $2^{i-1}$ 个数,然后整体交换其中两…