Java教程

高级图论

本文主要是介绍高级图论,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1. 同余最短路

说难也不算很难,挺有意思的一个知识点,不过应用不多。

前置知识:SPFA & Dijkstra 求最短路。

1.1. 算法简介

同余最短路常用来求解:给出 \(n\ (n\leq 50)\) 个数 \(a_i\ (1\leq a_i\leq 10^5)\),求在某个范围(\(10^{18}\))内有多少个数能够由这些数进行系数非负的线性组合得到。

由题意,对于一个数 \(r\),如果它可以被组合而成,那么任何 \(r+x_ia_i\) 也可以组合而成。但是同时考虑所有变量非常麻烦,时间复杂度也无法接受,所以我们将目光仅放在一个数 \(a_1\) 上

同余最短路的核心思想是:如果一个数 \(r\) 可以得到,那么任何 \(r+xa_1\) 也可以被得到。因此我们只需要找:对于每个模 \(a_1\) 同余的同余类,其中最小的能被组合出的数是什么。注意到 \(a_1\) 本身是较小的,所以对每个同余类求出最小数是可行的。而如果我们得到了模 \(a_1\) 余 \(j\) 的数中最小能被表示出来的数,设为 \(d_j\),那么可以通过加上 \(a_2\sim a_n\) 转移到其它同余类 \(d_k\ (k\equiv j+a_i\pmod {a_1})\ (2\leq i\leq n)\)。

注意到上述算法非常像一个最短路:对于每个点 \(j\),它向 \((j+a_i)\bmod a_1\) 连了一条长度为 \(a_i\) 的边,求每个点的最短路。因此使用 SPFA(不可能是网格图或其它奇奇怪怪的图,不会被卡)或 Dijkstra 即可。初始值 \(d_0=0\),\(d_i=\infty\ (1\leq i<a_1)\)。

求出 \(d_j\) 后得到答案是 trivial 的,不妨设我们需要求出 \([1,r]\) 有多少个符合要求的数,则答案为:

\[\sum_{i=0}^{a_1-1}\max\left(0,\dfrac{r-d_i}{a_1}+[i\neq 0]\right) \]

除法下取整,时间复杂度为 \(\mathcal{O}(na_1k)\)。

1.2. 例题

I. P2371 [国家集训队]墨墨的等式

是同余最短路的板子题。设 \(m=n\times a_i\)。由于图的形态很固定(不是网格图),所以使用 \(\mathcal{O}(mk)\) 的 SPFA 会比 \(\mathcal{O}(m\log m)\) 的 Dijkstra 快不少。

const int N = 5e5 + 5;
ll n, l, r, ans, a[N], d[N];
queue <int> q;

int main(){
	cin >> n >> l >> r;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	mem(d, 0x3f, N), d[0] = 0, q.push(0);
	while(!q.empty()) {
		ll t = q.front(); q.pop();
		for(int i = 2; i <= n; i++) {
			ll to = (t + a[i]) % a[1], v = d[t] + a[i];
			if(d[to] > v) d[to] = v, q.push(to);
		}
	}
	for(int i = 0; i < a[1]; i++) {
		ll h1 = l - d[i] - 1, h2 = r - d[i];
		if(h1 >= 0) ans -= h1 / a[1] + 1;
		if(h2 >= 0) ans += h2 / a[1] + 1;
	} cout << ans << endl;
	return 0;
}
这篇关于高级图论的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!