Gravatar
qwq
积分:26
提交:9 / 17

Pro1787  月考统计

首先很容易想到差分约束

一个条件相当于 $x_i-x_j\le w(i,j)\iff x_i\le w(i,j)+x_j$,考虑从 $j$ 到 $i$ 连边,边权为 $w(i,j)$

考虑某个 $x_i-x_j$ 最小是多少,发现其实就是图中 $i\to j$ 的最短路的相反数。

因此,设 $\text{dis}(i,j)$ 表示 $i\to j$ 的最短路长度,那么我们只需要找到 $\min_{j\neq i}\text{dis}(i,j)$ 即可。

考虑分治。定义 $\text{solve}(l,r)$ 表示计算 $[l,r]$ 内每个点对 $[l,r]$ 内自己的贡献;设 $mid=(l+r)/2$,我们建一个源点 $s$ 并向每个 $x\in[l,mid]$ 连边,从 $s$ 开始跑 SPFA,就算出了 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。

同理也可以算出 $[mid+1,r]$ 到 $[l,mid]$ 的贡献;分治的边界是 $l=r$,此时直接返回即可。可以发现分治完成之后,我们就算出了 $[1,n]$ 中每个点的答案。

代码实现的方式大概是对每一位分 $0,1$ 考虑,和分治本质是等价的。

代码并不难写,不到 100 行,一张图就能截下来





2023-01-29 11:45:00    
我有话要说
暂无人分享评论!