CF1354F Summoning Minions
CodeforcesLuogu分析有几个比较显然的结论（证明不会）：一定存在一组最优解，使得所有卡都被摆上去过。感性理解：因为 $b_i\geq 0$ 所以你就算摆上去再拿下来也不会更差。一定存在一组最优解，满足首先摆上 $k-1$ 张卡，再将 $n-k$ 张卡摆上去后立即拿下来，再将剩下的那张卡摆上去。感性理解：此时 $b_i$ 的贡献是最大的，且 $a_i$ 的贡献没有影响。那么相当于要...
标签 网络流 下的文章
- 首页
- 网络流
LOJ6045 「雅礼集训 2017 Day8」价
LOJCF 原题分析感觉很像最小权闭合子图。为了方便把所有费用取负。考虑这样的连边方式源点向每种药连容量为 $+\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]寿司餐厅
LuoguLOJ分析数组开小 -> 100->40 -> 身败名裂先考虑没有费用的情况，显然是最大权闭合子图模型（选了 $[i,j]$ 就必须选它的所有子区间）。因此对于每个 $[i,j]$，如果 $d_{i,j}$ 为正则从源点向它连容量为 $d_{i,j}$ 的边，否则从它向汇点连容量为 $-d_{i,j}$ 的边，然后对于每个 $[i,j]$ 向它的子区间连容量为 $...
洛谷5331 [SNOI2019]通信
LuoguLOJ分析容易想到一个费用流，即将每个哨站拆成两个点 $i$ 和 $i'$，然后源点向 $i$ 连容量为 $1$ 费用为 $0$ 的边，$i$ 向汇点连容量为 $1$ 费用为 $W$ 的边，$i'$ 向汇点连容量为 $1$ 费用为 $0$ 的边，$i$ 向 $j'$（$i<j$）连容量为 $1$ 费用为 $|a_i-a_j|$ 的边，然后求最小费用最大流即可。然而这样子边数是...
洛谷5470 [NOI2019]序列
LuoguLOJ分析至少有 $L$ 个下标相同 $\Longleftrightarrow$ 至多有 $K-L$ 个下标不同。考虑一个费用流模型，即从源点向 $a$ 中所有点连容量为 $1$、费用为 $a_i$ 的边，从 $b$ 中所有点向汇点连容量为 $1$、费用为 $b_i$ 的边，从 $a_i$ 向 $b_i$ 连容量为 $1$、费用为 $0$ 的边，再新建两个点 $C,D$，从 $C$...
CF724E Goods transportation
CodeforcesLuogu分析容易想到一个网络流做法，即源点向每个点连容量为 $p_i$ 的边，每个点向汇点连容量为 $s_i$ 的边，每个点向编号比它大的点连容量为 $c$ 的边，然后求最大流即可。发现最大流不好求，而图比较特殊，可以考虑 DP 求最小割。设 $dp_{i,j}$ 表示前 $i$ 个点有 $j$ 个点和源点相连的最小割。转移这样考虑：如果 $i$ 与源点相连，则断掉连向...
BZOJ3218 a + b Problem
BZOJ分析容易看出最小割。考虑连边：对于每个方格，从 $s$ 向它连容量为 $b_i$ 的边，从它向 $t$ 连容量为 $w_i$ 的边。对于每个方格，新建一个节点 $i'$，从 $i$ 向 $i'$ 连容量为 $p_i$ 的边，从 $i'$ 向 $a_j\in [l_i,r_i]$ 且 $j<i$ 的方格 $j$ 连容量为 $+\infty$ 的边。考虑正确性：显然对于每个方格，$...
51nod1325 两棵树的问题
51nod分析考虑钦定一个点一定在选出的子集中。我们把钦定的这个点作为根，那么如果 $x$ 在子集中，则 $x$ 在两棵树上的父节点都应该在子集中。那么问题就转化成了最大权闭合子图，直接网络流即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ /...
洛谷4518 [JSOI2018]绝地反击
LuoguLOJ分析设 $f(\alpha)$ 为正多边形旋转角度为 $\alpha$ 时的最短时间，容易发现 $f(\alpha)$ 是单谷的，因此可以三分 $\alpha$。考虑如何计算 $f(\alpha)$。二分 $f(\alpha)$ 的值 $t$，如果某艘飞船在 $t$ 时间内能够到某个位置则它们可以匹配，判断是否存在完美匹配即可。这样子可能过不了，考虑一些优化。我们预处理出每艘...