officeyutong

平面图最小割转对偶图最短路。

#include

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

每种代号新建一个点，权值为代号的平方乘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

最大权闭合子图。

输出方案？

注意到所有割边要么和源点相连，要么和汇点相连。

故从源点开始BFS，能走到的点全都在源点集合内。

#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$都是成立的，再大的没法跑了。

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

//

考虑如何转换成普通的二分图棋盘模型？

一个炸弹的攻击区域，则这些列对应的区域不能再放炸弹。

枚举出每行每列连续的不包括#的区域。

每个视为一个点，有交叉就连边。

#include

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

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

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

然后跑最小可行流即可。

#include