prologue

都快 csp-s 了还啥也不会的废柴一根，~~真不知道能不能进队（痴人说梦）~~。

main body

同余最短路的适用题型

当出现形如「给定 n 个整数，求这 n 个整数能拼凑出多少的其他整数（n 个整数可以重复取）」，以及「给定 n 个整数，求这 n 个整数不能拼凑出的最小（最大）的整数」，或者「至少要拼几次才能拼出模 K 余 p 的数」的问题时可以使用同余最短路的方法。

看到上述的问题，其实很像完全背包，但是你如果开个完全背包很容易就 MLE 喜提0pts 的好成绩，所以我们考虑出来的一种优化方法，优化掉空间，从而实现大跃进（ 0pts -> 100pts

同余最短路的通见转移形式

通常我们面对一个题目可以推出来如下的式子:

\[f_{i + y} \gets f_i + y \]

我们很容易类比到单源最短路。（~~哪里容易，要不是学了我能想到这？~~）

\[dis_{i + y} = dis_u + edge_{u \to v} \]

例题

标签：短路,0pts,整数,拼凑出,同余,dis
From： https://www.cnblogs.com/carp-oier/p/17744327.html

Johnson 全源最短路
Johnson全源最短路Johnson和Floyd一样是能求出无负环图上任意两点间最短路径的算法。引入求任意两点间的最短路可以通过枚举起点，跑$n$次SPFA来解决，时间复杂度是$O(n^2m)$的，也可以用Floyd解决，复杂度为$O(n^3)$。或者我们可以跑$n$次堆优化的Dijkstra，......
P1144 最短路计数题解
Problem考察算法：拓扑排序+$DP$+$Dijkstra$。题目简述给出一个无向无权图，问从顶点$1$开始，到其他每个点的最短路有几条。思路先求出$1$号点到每个点的最短路$d_i$。分析每条边$(x,y)$：如果d[x]+1==d[y]：这条边有用。将所有有用的边拓扑排序......
853. 有边数限制的最短路
第一版err#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<cmath>#defineN505usingnamespacestd;intn,m,k,dis[N],cnt,hd[N],vis[N],x,y,z;structEdge{intto,nxt......
单源最短路模板
SPFA#include<bits/stdc++.h>#definerintregisterint#defineendl'\n'usingnamespacestd;constintN=1e5+5;constintM=1e6+5;constintinf=1e9;inth[N],e[M],ne[M],dist[N],w[M];intn,m,s,idx;queue<int>......
[算法分析与设计] 1. 全源最短路近似
全源最短路(APSP)近似。有两种近似stretch$k$.$\delta(u,v)\leqd(u,v)\leqk\cdot\delta(u,v)$.surplus$t$.$\delta(u,v)\leqd(u,v)\leq\delta(u,v)+t$.其中，$\delta(u,v)$表示$u,v$间真实的最短路长度。先来考虑无权图上的surplus......
最短路与次短路
最短路算法不再赘述，假定我们已经求出了最短路，记$f[x,y]$为$x$到$y$的最短路。记$g[x,y]$为$x$到$y$的严格次短路。最短路树的定义单源最短路问题中，如果p1->p2->p3->...pn是一条最短路，就将它的边都加入图中。将所有的最短路径都这样处理，得到的图就......
P7916 [CSP-S 2021] 交通规划 sol-最短路+环形dp
P7916[CSP-S2021]交通规划solStatement传送门Solution好题。发现$k\le2$的分值非常多，于是我们考虑从$k=2$入手。颜色相同就不用说了，直接染成同一种颜色就行了。我们考虑其他情况，就是颜色不相同的情况，我们一定是找了一条路径把这个图给切开了就像这个样子。......
最短路基础实现方法模板合集
$\color{#39c588}{关于最短路}$$\color{purple}{首先是最短路的算法选择思路捏,直接来个Y总的图}$++$\color{purple}{单源汇问题}$++$\color{orange}{朴素版Dijkstra}$实现思路//朴素版Dijkstrao(n^2)--处理稠密图--稠密图用邻接矩阵存储//1.初始化邻接......
数论——线性同余方程、乘法逆元学习笔记
数论——线性同余方程、乘法逆元众所周知：说明除非特殊说明，以下提到的exgcd函数均定义为：//ax+by=gcd(a,b)llexgcd(lla,llb,ll&x,ll&y,lld=0){if(b==0)x=1,y=0,d=a;elsed=exgcd(b,a%b,y,x),y-=a/b*x;return......
同余最短路
简述：完全背包，但物品质量很大（105左右），空间上第二维开不下，时间上狠狠超时，咋办呐，同余最短路咯（不小心学到的）先简写f[(i+aj)%m]=min( f[(i+aj)%m],f[i]+aj)类比最短路Dijkstra咋求的d[y]=min(d[y],d[x]+vx,y)sox->i,y->(i+aj)%m,x->y建一条有向边，最......

同余最短路

prologue

main body

同余最短路的适用题型

同余最短路的通见转移形式

例题

相关文章

赞助商

阅读排行