洛谷5470 [NOI2019]序列
Luogu LOJ 分析 至少有 $L$ 个下标相同 $\Longleftrightarrow$ 至多有 $K-L$ 个下标不同。 考虑一个费用流模型，即从源点向 $a$ 中所有点连容量为 $1$、费用为 $a_i$ 的边，从 $b$ 中所有点向汇点连容量为 $1$、费用为 $b_i$ 的边，从 $a_i$ 向 $b_i$ 连容量为 $1$、费用为 $0$ 的边，再新建两个点 $C,D$，从...
标签 网络流 下的文章
- 首页
- 网络流
CF724E Goods transportation
Codeforces Luogu 分析 容易想到一个网络流做法，即源点向每个点连容量为 $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$ 的边。 考虑正确性...
洛谷4518 [JSOI2018]绝地反击
Luogu LOJ 分析 设 $f(\alpha)$ 为正多边形旋转角度为 $\alpha$ 时的最短时间，容易发现 $f(\alpha)$ 是单谷的，因此可以三分 $\alpha$。 考虑如何计算 $f(\alpha)$。二分 $f(\alpha)$ 的值 $t$，如果某艘飞船在 $t$ 时间内能够到某个位置则它们可以匹配，判断是否存在完美匹配即可。 这样子可能过不了，考虑一些优化。我们预...
洛谷3980 [NOI2008]志愿者招募
Luogu 分析 这是一个线性规划做法。下面举的栗子为样例。 设 $X_i$ 为第 $i$ 类志愿者的招募数，$P_i$ 为第 $i$ 天招募志愿者的数量，那么可以列出一些不等式 注意到每个变量恰出现 $2$ 次且系数一正一负。 我们可以把每个等式看做一个点，正数代表流出，负数代表流入，那么等式相当于流量平衡。 因此我们得到了这样的建图方法： 如果 $P_i-P_{i-1}>0$，...
CF343E Pumping Stations
Codeforces Luogu 分析 显然先把最小割树建出来。 首先有一个结论：第一问答案的上界为最小割树上所有边权之和。 下面考虑怎样达到这个上界。 考虑最小割树上的最小边，我们应让它只被经过一次。设它的两个端点为 $a_i,a_{i+1}$ ，则 $a_{1..i-1}$ 中任意两点不经过该边，$a_{i+2..n}$ 中任意两点不经过该边。于是将该边断掉后两边递归处理即可。 代码 /...
洛谷4249 [WC2007]剪刀石头布
Luogu 分析 首先三元环个数不是很好算，考虑用总数减去不是三元环的。 总数显然是 考虑三个点要怎样才不会构成三元环，可以发现有一个点的入度为 $2$ 即可。 进一步发现，如果 $u$ 的入度为 $d$ ，那么整张图会产生 $d\choose 2$ 个不是三元环的三元组。 考虑差分。对于一个点 $u$ ，如果它的入度增加了 $1$ 变成了 $deg$ ，那么整张图会减少 $deg-1$ ...
洛谷3288 [SCOI2014]方伯伯运椰子
Luogu 分析 显然调整后总交通量不变是最佳的，因为不能减少，并且增加的话费用一定会变大。 发现压缩操作很像网络流中的退流，扩充操作很像网络流中的增广。 所以对于原图中的每条边 $(u,v,a,b,c,d)$ ，新建两条边： $v\to u$ ，边权为 $a-d$ （如果 $c=0$ ，不要建这条边）。对应压缩。 $u\to v$ ，边权为 $b+d$ 。对应扩充。 发现在这张图跑，经...
CF802C Heidi and Library (hard)
CodeForces 分析 首先将每天拆成两个点，入点 $s_i$ 和出点 $t_i$ 。 考虑怎么建图： 从源点向 $s_i$ 连容量为 $1$ 、费用为 $c_{a_i}$ 的边，表示每本书。 从 $s_i$ 向 $s_{i+1}$ 连容量为 $k-1$ 、费用为 $0$ 的边，表示第 $i$ 天最多留 $k-1$ 本书。 从 $s_i$ 向 $t_i$ 连容量为 $1$ 、费用为 $...
洛谷4307 [JSOI2009]球队收益
Luogu 分析 考虑费用流。对于每个球队建一个点，向汇点连边；对于每场比赛建一个点，从源点向其连 $1$ 边、其向对应的两个球队连 $1$ 边，表示只有一个队能赢球。 考虑加入费用。注意到 $x+y$ 固定，于是 $Cx^2 + Dy^2$ 是关于 $x$ 的凹函数，因此可以使用费用递增的技巧。具体的，我们先将后面全负的代价算入答案中，然后依次连费用为 $C(x + 1)^2 + D(y ...