「OI之路」07图论-8第k优解相关

第k优解相关
主要是「寻找第k优解的几种方法————俞鼎力」的学习笔记

区间k大的众多拓展

暂未研究

k小生成树

暂未研究

k短简单路径

暂未研究

k短路

无负权边下
对反图上终点建最短路径树
然后每个点,存储一个非树边序列
因为树上父亲是当前的序列的子集,继承过来,然后加入新的非树边(单个)
那么为了减少状态的出度,从最基础的「在后面直接加边」改为「排序后,有序替换」,这个感觉论文的图不错
那么每个点,开一个堆去维护,因为有继承的环节,用可持久化左偏树会非常方便,复杂度为严格logn(深度限制)
$O(nlogn+mlogm+klogk)$
似乎实现有很多边界和细节?
暂未达成: $O(nlogn+m+klogk)$ (不过反正连supergaymj都不会……)
以后补代码……

k优多个数列选数

例题:POJ2442 Sequence,loj6254 最优卡组code
核心思想:状态不能也没必要压缩,但我们并不需要存储状态,而是像dp一样存储转移所需要的信息
既然我们存储转移信息,我们就不能hash,需要保证选数方案是一棵树,也就是只有一个前继转移
做法:klogk
先把没有意义的ci=1的数列去除,然后每个数列递减排序并差分,按照「最大-次大」给数列间递增排序
三元组(i,j,sum)表示前i行已经处理,第i行至少选择第j个,然后后面的n-i行都选择最大值
$(i,j,sum)->(i,j+1,sum-a[i][j]),(i+1,2,sum-a[i+1][2])$
$(i,2,sum)->(i+1,2,sum+a[i][2]-a[i+1][2]),即这行依然选择最大$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c623.html
转载请注明出处,谢谢!