首页 > 其他分享 >同余最短路的转圈技巧

同余最短路的转圈技巧

时间:2023-07-06 10:44:26浏览次数:43  
标签:背包 frac int 短路 转圈 体积 物品 同余

同余最短路还在写最短路?感觉不如转圈!

众所周知,在同余最短路算法中,我们选取一个基准物品的体积作为模数 \(m\),并对其它物品的体积 \(v_i\) 和所有 \(0\leq i < m\),从 \(i\) 向 \((i + v_i)\bmod m\) 连权值为 \(v_i\) 的边,跑最短路。

算法介绍

实际上,存在简单的不需要最短路的做法。

不要从图论的角度考虑问题,而是回归本源:完全背包。更具体地,体积模 \(m\) 意义下的完全背包。对于体积为 \(v_i\) 的物品,它在长度为 \(m\) 的环上形成 \(d = \gcd(v_i, m)\) 个子环。从一个点出发,不可能绕着子环走一圈再转移回到该点,因为最短路不会经过同一个点两次,否则存在负环。另一种理解方式是,如果绕着环走了一圈,相当于选择了 \(\frac m d\) 个体积为 \(v_i\) 的物品,而这些物品可以替换为若干基准物品而被忽略,使得总体积更小。进一步地,如果重复经过同一个点,那么可以将这两次经过之间加入的所有物品替换为若干基准物品

因此,往背包加入体积为 \(v_i\) 的物品时,至多加入 \(\frac {m} {\gcd(v_i, m)} - 1\) 个。对于每一个子环,我们绕着这个环转两圈,即可考虑到所有转移,因为每个点都转移到了子环上的其它所有点。时间复杂度 \(\mathcal{O}(nm)\)。

for(int i = 0, lim = __gcd(v[i], m); i < lim; i++)
  for(int j = i, c = 0; c < 2; c += j == i) {
    int p = (j + v[i]) % m;
    f[p] = min(f[p], f[j] + v[i]), j = p;
  }

对于普通的完全背包,即边权等于 \(v_i\) 的问题,我们找到子环上权值最小的点,绕着环转移一圈即可(daklqw)。但是写起来不如转两圈简洁。

例题

P2371 墨墨的等式

以下是经典题墨墨的等式的转圈代码。它是普通的完全背包。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, a[N];
long long f[N], l, r, ans;
int main() {
  cin >> n >> l >> r;
  for(int i = 1; i <= n; i++) cin >> a[i];
  memset(f, 0x3f, sizeof(f)), f[0] = 0;
  sort(a + 1, a + n + 1), m = a[1];
  for(int i = 2; i <= n; i++)
    for(int j = 0, lim = __gcd(a[i], m); j < lim; j++)
      for(int t = j, c = 0; c < 2; c += t == j) {
        int p = (t + a[i]) % m;
        f[p] = min(f[p], f[t] + a[i]), t = p;
      }
  for(int i = 0; i < a[1]; i++) {
    if(r >= f[i]) ans += max(0ll, (r - f[i]) / a[1] + 1);
    if(l > f[i]) ans -= max(0ll, (l - 1 - f[i]) / a[1] + 1);
  }
  cout << ans << endl;
  return 0;
}

P9140 背包

背包这道题目在完全背包的可行性基础上加入了权值这一维度。

注意到,如果我们将 \(\frac {c_i}{v_i}\) 最大的物品选做基准物品,设其体积为 \(m\),价值为 \(w\),那么我们同样不会经过同一个点,原因是类似的:因为 \(\frac {c_i} {v_i}\leq \frac w m\),所以如果若干其它物品可以替换为若干基准物品,我们一定会这么做,以最大化单位体积贡献的价值。

但是,对于两组背包方案 \((V_1, C_1)\) 和 \((V_2, C_2)\),若 \(V_1\equiv V_2\pmod m\),该如何衡量这两组方案的优劣呢?

对于一组背包方案 \((V', C')\) 和一次查询 \(V\),若 \(V'\equiv V\pmod m\) 且 \(V' \leq V\),则其最终权值为 \(C' + \frac {V - V'} mw\)。因此,对于相同剩余系的所有背包方案 \((V', C')\),我们希望最大化 \(C' - \lfloor\frac {V'} {m}\rfloor w\),转化到图论就是 “最长路” 的 \(dist\)。也就是说,当我们需要通过加入物品 \((v_i, c_i)\) 从 \(p\) 转移到 \(q = (p + v_i)\bmod m\) 时,用于更新 \(f_q\) 的值等于 \(f_p + c_i - \lfloor \frac {p + v_i} {m}\rfloor w\)。

而根据 \(\frac {w} {m}\) 的最大性,这样一张包含正负权边的图上不可能存在正权环(求最长路)。又因为不经过重复点,所以每组剩余系的最优方案对应的 \(V'\) 均不超过 \(m ^ 2\) 即 \(10 ^ {10}\),配合 \(V\geq 10 ^ {11}\) 的限制保证了正确性。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 5;
ll n, q, m = 1, w, V, f[N], c[55], v[55];
int main() {
  cin >> n >> q;
  for(int i = 1; i <= n; i++) {
    cin >> v[i] >> c[i];
    if(w * v[i] < m * c[i]) w = c[i], m = v[i];
  }
  for(int i = 1; i < m; i++) f[i] = -1e18;
  for(int i = 1; i <= n; i++)
    for(int j = 0, lim = __gcd(v[i], m); j < lim; j++)
      for(int t = j, _ = 0; _ < 2; _ += t == j) {
        int q = (t + v[i]) % m;
        f[q] = max(f[q], f[t] + c[i] - ((t + v[i]) / m) * w), t = q;
      }
  for(int i = 1; i <= q; i++) {
    cin >> V;
    int p = V % m;
    if(f[p] < -1e17) cout << "-1\n";
    else cout << f[p] + V / m * w << "\n";
  }
  return 0;
}

和其它算法的对比

例题一的转圈技巧并没有 SPFA 跑得快。SPFA 跑同余最短路的复杂度依然是个谜。它的理论上界是 \(\mathcal{O}(|V||E|)\) 即 \(\mathcal{O}(nm ^ 2)\),但实际表现比小常数 \(\mathcal{O}(nm)\) 还要优秀。

此外,在可以使用最大体积作为基准元素时,令 \(f_i\) 除以 \(m\) 下取整得 \(f'_i\),则 \(f_i = f'_i m + i\)。对于 \(f'\),边权只有 \(0\) 或 \(1\),01-BFS(FZzzz)。

很显然,转圈技巧比最短路做法好写,且适用范围没有任何限制(如 01-BFS 就无法解决第二道例题)。

总结

有趣的是,同余最短路不应该从最短路的角度考虑。其本质上是根据单调性值域定义域互换后将完全背包转化为体积模 \(m\) 意义下的完全背包。普通完全背包的转移是有向无环图,而环上完全背包转移成环,这让我们想到最短路。但因为一个点不会经过它自己,对应原问题就是对于一个物品,不会使得它的总体积为基准物品体积的倍数,所以,我们可以将完全背包转化为类多重背包问题。

笔者在研究「背包」一题的官方解法时,惊讶于其 “转两圈” 思想的巧妙和自己从来没有听说过这个技巧。翻了一遍经典同余最短路题目的题解区,也没找到几篇除了 SPFA 和 Dijkstra 以外的题解,故将其分享给各位读者。

同余最短路还在写最短路?时代的眼泪!

标签:背包,frac,int,短路,转圈,体积,物品,同余
From: https://www.cnblogs.com/alex-wei/p/17531487.html

相关文章

  • 最短路
    BFS求最短路BFS可用于求无权图的最短路,时间复杂度为\(O(m)\),\(m\)为图上边的数量。Floyd求最短路Floyd用于求任意两点的最短路径,使用于任意图,无论有向无向,正权负权。时间复杂度为\(O(n^3)\),\(n\)为节点数量。设\(dp[i][j]\)是从\(i\)点到\(j\)的最短路径,最开始时每两个点之间......
  • 同余
     求逆例题1:P1082[NOIP2012提高组]同余方程模板题,使用拓展欧几里得算法求逆代码:#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llgcd(lla,llb,ll&x,ll&y){ if(b==0){ x=1;y=0; returna; } lld=gcd(b,a%b,y,x); y-=a/b*x; returnd......
  • 使用uni.app 里面 uni.chooseLocation api 打开地图位置 踩坑 踩坑 地图搜索 和列
    用 Android基座可以正常使用真机调试也可以用就是打包的时候打包完毕弹出地图之后搜索一直转圈  地图列表没有东西也是一直转圈里面有好多踩坑点  太狗了  要打包的 包名  和 dcloud里面的包名 和如果用高德地图里面的  packagename三......
  • thinkphp6多用用模式下缩短路由
    场景描述:要做seo,要缩短路由。原xxx.com/home/article/1改为xxx.com/article/1解决办法:index.php<?php//+----------------------------------------------------------------------//|ThinkPHP[WECANDOITJUSTTHINK]//+---------------------------------------......
  • 38. 最短路径
    一、什么是最短路径  在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径,这条路径就是两点之间的最短路径(ShortestPath),其中第一个顶点为源点(Source),最后一个顶点为终点(Destination)。单源最短路径问题:从某固定源点触发,求其到所有其它顶点的最短路径;多源......
  • 感应电机 异步电机定子匝间短路仿真 matlab simulink
    感应电机异步电机定子匝间短路仿真matlabsimulink我将重新表述关于感应电机和异步电机定子匝间短路仿真的内容。感应电机是一种常见的电动机类型,它通过感应原理工作。异步电机是感应电机的一种特殊类型,其定子匝间短路是指在定子绕组中存在短路现象。仿真是使用计算机模型来模拟......
  • 浅谈类 k 短路问题
    u群题题意:\(n\)个数,对于所有大小在\([L,R]\)内的子集求和并排序,求前\(k\)小子集的信息。排序,记数组为\(a_{1,\cdots,n}\)。先考虑\(L=R\)的情况。最小的子集一定是\(a_{1,\cdots,L}\),第二小则是将\(a_L\)改为\(a_{L+1}\),推广到更一般的情况——我们以\([1,L]\)......
  • 6-2 最短路径(迪杰斯特拉算法)
    试实现迪杰斯特拉最短路径算法。函数接口定义: voidShortestPath_DIJ(AMGraphG,intv0); 其中 G 是基于邻接矩阵存储表示的有向图, v0表示源点裁判测试程序样例: #include<iostream>usingnamespacestd;#defineMaxInt32767#defineMVNum100typedefchar......
  • JS 短路运算
    Boolean强制转换:除了NaN、null、""、undefined、0、function这几个为false外,其他皆为true。短路运算的符号:   ||  && ! 或与非。短路运算的原理:当有多个表达式时,左边的表达式值可以确定结果时,就不再继续运算右边的表达式的值。短路运算的规则:&&找假,先看第一个表达式的......
  • 最短路算法
    目录最短路算法单源最短路-迪杰斯特拉算法最短路算法单源最短路-迪杰斯特拉算法用于计算一个节点到其他所有节点的最短路径Dijkstra算法是贪心算法,是一种求解非负权图上单源最短路径的算法。基本思想是:设置一个顶点的集合S,并不断地扩充这个集合,当且仅当从源点到某个点的路......