高级图论

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

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]\) 有多少个符合要求的数，则答案为：

除法下取整，时间复杂度为 \(\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;
}

这篇关于高级图论的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！