代码备份

$ca=\lceil {a\over k}\rceil$

$n个城市，m条有向边，(u,v,c,p,plimit)代表经过u\to v这条一次需要花费c的代价$
$并且有p的几率使得整个网络拥堵，要保证经过这条边的发生拥堵概率不超过plimit$
$给出sCnt个仓库所在的城市，并给出(s_i,have_i)，s_i拥有have_i的存储量$
$给出tCnt个需求所在的城市，并给出(t_i,need_i)，t_i拥有need_i的存储量$
$输出最小花费，以及最小花费下最小化的拥堵概率$

$做法大概是：$
$拥堵概率计算，假设经过x次，prob=\sum_{i=1}^x (1-p)^{x-1}\cdot p$
$反过来思考即，prob=1-(1-p)^x$
$最小化prob=最大化(1-p)^x，取个自然对数即\sum_{i=1}^xln(1-p)$
$根据费用流问题需要最小化，取负就好了即-\sum_{i=1}^xln(1-p)$
$那么边权由p变为了-ln(1-p)，并且这个数值是正的，不会有负圈的问题$
$对于双权只要把前一个权乘一个很大的值D(D>\displaystyle\sum_{flow}-ln(1-p))就可以了$
$这个是可以证明的，即新的权w=c\times D+(-ln(1-p))$
$对于不超过plimits，即为1-(1-p)^x\le plimit，那么x\le log_{1-p}{1-plimit}$
$之后跑多源多汇的费用流就可以了$

$s1是母串，s2是模式串，|s1|=n，|s2|=m，n\ge m$
$f[i+m]=\sum_{j=0}^{m-1}(s1[i+j]-s2[m-j])^2$

$f_i = \sum_{j=0}^i A_i * B_{i-j}$

$问题抽象：假设现在有权值集合U，每个权\in \mathbb{Z^2} ，形如(a_i,\ b_i)$
$选择k>0个权的子集S，现要使得\displaystyle\sum_{j\in S} a_j最大，相等的情况下，其次\displaystyle\sum_{j\in S} b_j最大$
$现要将双权问题转化成单权问题$
$由问题可知，需构造某种映射方案f(x)使得满足原本的偏序关系$
$即令X=(a_x,\ b_x)，Y=(a_y,\ b_y)，若X\ge Y，那么f(X)\ge f(Y)$
$构造如下方案：令\Delta=\displaystyle\sum_{i\in U} b_i + 1，对于X=(a_x,\ b_x)，则f(X)=a_x\cdot \Delta+b_x$
$同理，Y=(a_y,\ b_y)，则f(Y)=a_y\cdot \Delta+b_y$
$同理，Z=(a_z,\ b_z)，则f(Z)=a_z\cdot \Delta+b_z$
$易知，任意X\ge X，且有f(X)\ge f(X)，满足自反性$
$易知，若X\ge Y且Y\ge X，即f(X)\ge f(Y)且f(Y)\ge f(X)，可得f(X)=f(Y)，满足反对称性$
$易知，若X\ge Y且Y\ge Z，即f(X)\ge f(Y)且f(Y)\ge f(Z)，可得f(X)\ge f(Z)，满足传递性$
$所以，构造方案满足原本的偏序关系，原问题得证$
$\blacksquare$