同余最短路还在写最短路?感觉不如转圈!
众所周知,在同余最短路算法中,我们选取一个基准物品的体积作为模数 \(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