注意到每个权值只计算一次,考虑最大权闭合子图。

每种代号新建一个点,权值为代号的平方乘m。

每种寿司的权值为它本身的代号,向他代号对应的点连边。

每个区间新建一个点,权值是他的代价,同时向这个区间的子区间和这个区间内的所有寿司连边。

#include
阅读全文..

考虑最大流最小割。

如果忽略相邻两个切点之间的高度差限制,那么可以直接从点$(r,c,h)$向点$(r,c,h+1)$连接一条容量为$A_{(r,c,h)}$的边,最后的最小割就是答案。

如果带上距离差的限制呢?

如果切点选择为$(r,c,h)$,那么对于一个相邻的切点$(r_1,c_1,h_1)$,$h_1$一定不能小于$h-d$,即小于$h$的$h_1$不能与$(r,c,h)$划定在同一个割集里。

连边$(r,c,h)$到$(r_1,c_1,h-d)$,其中$(r_1,c_1)$与$(r,c,)$相邻,边权为$\infty$,表示在切掉点$(r,c,h)$的出边后,相邻点切掉的出边不得在$(r_1,c_1,h-d)$之下。

#include
阅读全文..

首先因为只能从编号较小的点向较大的点走,所以无向边重定向为有向边。

对于重定向后的图,一定是DAG。

考虑一个模型,每个点$vtx$拆为两个点$vtx_0$和$vtx_1$,建立一张二分图,源点向所有的$vtx_0$连边,流量为1费用为0,所有$vtx_1$向汇点连边,容量为1费用为0。

源点向所有$vtx_1$连边,流量1费用为传送到这个点的代价,表示直接传送到这个点。

对于一条边$(u,v,cost)$,连接边$u_0$到$v_1$,流量1费用$cost$。

然后跑最小费用最大流即可。

对于一条路径,它的起点要么从其他点经过边而来,要么传送而来,故这样可以覆盖掉所有的点。

#include
阅读全文..

$$ \text{注意到}F_k\left( n \right) \text{是积性函数} \\ \text{对于质数幂}F_k\left( p^c \right) =\sum_{0\le i\le c}{F}_{k-1}\left( p^i \right) \\ \text{可以注意到}F_k\left( p^c \right) \text{的取值与}p\text{无关} \\ \text{设}F_k\left( p^n \right) \text{的生成函数为}G_k\left( x \right) =\sum_{n\ge 0}{F}_k\left( p^n \right) x^n \\ \text{由上述可得}G_k\left( x \right) =\frac{G_{k-1}\left( x \right)}{1-x} \\ \text{其中}G_0\left( x \right) =\frac{1}{1-x} \\ \text{故}G_k\left( x \right) =\frac{1}{\left( 1-x \right) ^{k+1}} \\ F_k\left( p^n \right) =\left( \begin{array}{c} n+k\\ n\\ \end{array} \right) \\ \text{同时又注意到,}F_k\left( p_{1}^{c_1}p_{2}^{c_2}p_{3}^{c_3}....p_{t}^{c_t} \right) \text{的取值只与}\left\{ c_1,c_2....c_t \right\} \text{有关。} \\ \text{注意到可行状态只有244种。} \\ \text{同时又注意到,}\prod_i{\left( \begin{array}{c} c_i+x\\ c_i\\ \end{array} \right)}\text{是一个关于}x\text{的}\sum_i{c_i}\text{次多项式。} \\ \text{同时}\sum_i{c_i}\text{的取值上界为}O\left( \log n \right) \\ \text{故可以通过高斯消元求出这个多项式,进而可以}O\left( \log n \right) \text{时间计算}F\left( \prod_i{p_i^{c_i}} \right) \\ $$

#include
阅读全文..

大力猜一顿结论:

如果两个数$i$和$j$,满足$a_i$和$a_j$均不满足题目里给定的两个条件,就在$i$和$j$之间连接一条边,那么形成的图一定是一张二分图。

暴力跑一下跑到$1000$都是成立的,再大的没法跑了。

然后原题转化为二分图的最大带权独立集,最小割即可。

//
阅读全文..

给定一张DAG,可以花费1的代价覆盖一条路径,一条边可以被重复覆盖,求覆盖所有边最小代价。

原图建立一个网络,每条边的下界为1,表示这条边至少要被覆盖一次,上界为$\infty$,表示可以重复覆盖。

同时源点向每个点链连接下界为0的边,每个点向汇点连接下界为0的边。

然后跑最小可行流即可。

#include
阅读全文..