洛谷5331 [SNOI2019]通信
Luogu LOJ 分析 容易想到一个费用流，即将每个哨站拆成两个点 $i$ 和 $i'$，然后源点向 $i$ 连容量为 $1$ 费用为 $0$ 的边，$i$ 向汇点连容量为 $1$ 费用为 $W$ 的边，$i'$ 向汇点连容量为 $1$ 费用为 $0$ 的边，$i$ 向 $j'$（$i<j$）连容量为 $1$ 费用为 $|a_i-a_j|$ 的边，然后求最小费用最大流即可。 然而这样...
标签 网络流 下的文章
- 首页
- 网络流
洛谷6621 [省选联考 2020 A 卷]魔法商店
Luogu LOJ 分析 根据拟阵的相关理论可以知道：$A$ 是权值最小的基当且仅当 $\forall u\in A,v\notin A$，只要 $(A\backslash\{u\})\cup\{v\}$ 是基，则 $v_u\leq v_v$；权值最大的基的情况同理。这样子就把原题中最小值、最大值的限制转化成了若干组偏序关系。 现在的问题即为 $p=2$ 时的保序回归问题。根据论文中的理论，...
洛谷6967 [NEERC2016]Delight for a Cat
Luogu Gym 分析 考虑线性规划。设 $x_i$ 为第 $i$ 小时是否吃饭，可以列出线性规划 用 NOI2008 志愿者招募 一题的方法建图求最大费用最大流即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =======...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
洛谷3511 [POI2010]MOS-Bridges
Luogu LOJ 分析 考虑二分答案，则我们需要判定是否存在混合图欧拉回路。 首先混合图不连通的话一定不存在。 然后给无向边任意定向，算出每个点的度数，如果有点度数为奇数则不存在。 那么对于一条无向边，假设我们定向 $u\to v$，则我们可以改变它的方向使得 $in_u-out_u$ 增加 $2$、$in_v-out_v$ 减少 $2$。 因此可以考虑网络流。对于 $in_ out_i$...
洛谷5996 [PA2014]Muzeum
Luogu 分析 不难看出一个最大权闭合子图的模型，然而直接求最大流显然过不了，于是可以考虑模拟最大流。 首先把这个坐标系变换一下。如果警卫 $a$ 能看到手办 $b$，则应有 于是可以把 $(h\times x+w\times y,h\times x-w\times y)$ 作为每个点的坐标，这样子警卫 $a$ 能看到手办 $b$ 当且仅当 $x_b\leq x_a,y_a\leq y_...
CF1354F Summoning Minions
Codeforces Luogu 分析 有几个比较显然的结论（证明不会）： 一定存在一组最优解，使得所有卡都被摆上去过。感性理解：因为 $b_i\geq 0$ 所以你就算摆上去再拿下来也不会更差。 一定存在一组最优解，满足首先摆上 $k-1$ 张卡，再将 $n-k$ 张卡摆上去后立即拿下来，再将剩下的那张卡摆上去。感性理解：此时 $b_i$ 的贡献是最大的，且 $a_i$ 的贡献没有影响。...
LOJ6045 「雅礼集训 2017 Day8」价
LOJ CF 原题 分析 感觉很像最小权闭合子图。为了方便把所有费用取负。考虑这样的连边方式 源点向每种药连容量为 $+\infty+p_i$ 的边。 每种药向所需的药材连容量为 $+\infty$ 的边。 每种药材向汇点连容量为 $+\infty$ 的边。 拿最小割减去所有 $+\infty+p_i$ 的和即为答案（因为取了负）。 下面是正确性理解： 首先可以发现，第二种的边是不会割的...
LOJ6068 「2017 山东一轮集训 Day4」棋盘
LOJ 分析 考虑二分图。对于每一行、列被 # 隔开的每一段拿出来当做一个点，然后对于每个点从其所属的行连通块向列连通块连边。 但是每个连通块内可以放多个棋子。假设一个连通块内放了 $x$ 个棋子，那么会产生 $\frac{x(x-1)}{2}$ 的费用，我们要最小化费用。 考虑费用递增。由于 $\frac{(x+1)x}{2}-\frac{x(x-1)}{2}=x$，所以我们只需要连若干条...
洛谷3749 [六省联考2017]寿司餐厅
Luogu LOJ 分析 数组开小 -> 100->40 -> 身败名裂 先考虑没有费用的情况，显然是最大权闭合子图模型（选了 $[i,j]$ 就必须选它的所有子区间）。因此对于每个 $[i,j]$，如果 $d_{i,j}$ 为正则从源点向它连容量为 $d_{i,j}$ 的边，否则从它向汇点连容量为 $-d_{i,j}$ 的边，然后对于每个 $[i,j]$ 向它的子区间连容...