扩展Dijkstra

技术文章 7个月前 完美者
1,872 0

标签:最小值   使用   priority   get   ==   auto   理解   target   set   

本文从另一个角度理解Dijkstra算法,可能会与通常Dijkstra算法的讲解有一些区别。

 

最短路问题:给定有向图$G = (V, E)$,每条边形如$(x, y, w)$,其中$w$表示节点$x$至节点$y$的距离为$w \geq 0$。求节点$s$至节点$t$的最短路径长度。

Dijkstra算法:令$f(x)$表示节点$x$至节点$t$的最短路径长度。则

$$
f(x) = \min_{(x, y, w) \in E} f(y)+w,
$$

边界条件为$f(t) = 0$。

原理:我们可以通过迭代的方式计算出$f(x)$。初始状态取$f(x) = \infty (x \neq t)$以及$f(t) = 0$。迭代停止的条件为一次迭代后所有$f(x)$的值未发生变化。在迭代$n = |V|$次之后必然收敛。于是,我们可以得到一个$O(n(n+m))$的迭代算法,其中$m = |E|$。

优化的方式就是用一个堆模拟迭代。这个堆存放所有$f(y)$的值,每次取出最小的$f(y)$,那么这个$f(y)$在今后的迭代中不再变化,从而由它影响到的节点$x$必须满足$(x, y, w) \in E$,只需扩展$y$的所有反向边即可。因为每个节点只会从堆中取出一次,从而至多$O(n+m)$个值会因扩展而插入堆中,故复杂度为$O((n+m)\log (n+m))$。

注:使用Fibonacci堆可做到$O(m+n\log n)$。

 

CodeForces 1407E. Egor in the Republic of Dagestan

给定$n$个节点,$m$条边的有向图$G = (V, E)$,每条有向边形如$(x, y, c)$其中$c \in \{0, 1\}$。

要求给出一个节点染色方案$a_1, a_2, \dots, a_n \in \{0, 1\}$,使得对每个点$1 \leq x \leq n$,仅保留形如$(x, y, a_u)$的边后,节点$1$至节点$n$的最短路最大。$n, m \leq 10^5$。

解法:令$f(x)$表示节点$x$至节点$n$的最短路的最大可能值。则

$$
f(x) = \max_{c \in \{0, 1\}} \min_{(x, y, c) \in E} f(y)+1,
$$

边界条件为$f(n) = 0$。

初始状态为$f(x) = \infty (x \neq n)$以及$f(n) = 0$,迭代以上式子$n$次可收敛。从而得到一个$O(n(n+m))$的算法。

优化方式也是每次取出最小的$f(y)$来扩展即可,进而复杂度为$O((n+m)\log(n+m))$。由于这题边权为$1$,只需队列(BFS)而不需要堆即可取出最小值,故复杂度可做到$O(n+m)$。

参考代码:code

 

KickStart 2020 Round E. Golden Stone

给定$N$个节点,$M$条边的无向图$G = (V, E)$,一共有$S$种宝石,以及每个节点上拥有的宝石情况(拥有意味着无限资源)。

有$R$个打造方式,每个打造方式形如$(a_1, a_2, \dots, a_k) \to b$,其中$k \leq 3$,表示在同一个节点若集齐宝石$a_1, a_2, \dots, a_k$各一颗,可将他们打造成宝石$b$。

你可以以$1$单位花费,将一颗宝石从一个节点经过一条边运送到另一个节点。

求打造宝石$1$的最小花费。$N, M, S, R \leq 500$。

解法:令$f(x, c)$表示在节点$x$得到宝石$c$的最小花费。则

$$
f(x, c) = \min \begin{cases}
    f(y, c) + 1 & (x, y) \in E \\
    \sum_{i=1}^k f(x, a_i) & (a_1, a_2, \dots, a_k) \to b \land c \in \{a_i\}_{i=1}^k
\end{cases},
$$

边界条件为,$f(x, c) = 0$若节点$x$拥有宝石$c$。

初始状态为若节点$x$拥有宝石$c$则$f(x, c) = 0$否则$f(x, c) = \infty$,迭代以上式子$NS$次可收敛。从而得到一个$O((NS)^2(M+R))$的算法。

优化方式每次取出最小的$f(y, c)$扩展即可,时间复杂度为$O((NS+MS+NR)\log(NS+MS+NR))$。

参考代码:

void solve()
{
	int n, m, s, r;
	read(n, m, s, r);
	auto v = arr<vector<int>>(n + 1);
	for (int i = 1; i <= m; ++i)
	{
		int x, y;
		read(x, y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	auto has = arr<vector<int>>(n + 1);
	for (int i = 1; i <= n; ++i)
	{
		int k;
		read(k);
		vector<int> c(k);
		input(c);
		has[i] = c;
	}
	auto to = arr<vector<pair<int, vector<int>>>>(s + 1);
	for (int i = 1; i <= r; ++i)
	{
		int k;
		read(k);
		vector<int> a(k);
		input(a);
		int b;
		read(b);
		for (int x = 0; x < k; ++x)
		{
			vector<int> tmp;
			for (int y = 0; y < k; ++y) if (x != y) tmp.push_back(a[y]);
			to[a[x]].push_back({ b, tmp });
		}
	}

	const ll INF = 1000000000000LL;
	auto f = arr<ll>(n + 1, s + 1);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= s; ++j)
			f[i][j] = INF;
	struct node
	{
		ll val;
		int pos, color;
		bool operator < (const node& rhs) const
		{
			return val > rhs.val;
		}
	};
	priority_queue<node> q;
	for (int i = 1; i <= n; ++i)
	{
		for (auto c : has[i]) q.push({ 0, i, c });
	}
	while (!q.empty())
	{
		auto cur = q.top();
		q.pop();
		if (freshmin(f[cur.pos][cur.color], cur.val))
		{
			for (auto nxt : v[cur.pos])
			{
				if (cur.val + 1 < INF) q.push({ cur.val + 1, nxt, cur.color });
			}
			for (auto& e : to[cur.color])
			{
				const int& b = e.first;
				const vector<int>& a = e.second;
				ll tmp = cur.val;
				for (auto c : a) tmp += f[cur.pos][c];
				if (tmp < INF) q.push({ tmp, cur.pos, b });
			}
		}
	}
	ll res = INF;
	for (int i = 1; i <= n; ++i) freshmin(res, f[i][1]);
	if (res == INF) res = -1;
	writeln(res);
}

  

 

CodeForces 1387C. Viruses

给你一个上下文无关文法$G = (V, \Sigma, R)$,其中

  • $V = \{2, \dots, n-1\}$是非终结符的集合;
  • $\Sigma = \{0, 1\}$是终结符的集合;
  • $R \subseteq V \times (V \cup \Sigma)^+$是产生式的集合。

特别地,这个上下文无关文法不会产生空串,即$\epsilon \notin L(G)$。

同时给出$m$个字符串$s_1, s_2, \dots, s_m \in \{0, 1\}^+$。若字符串$s$是$t$的子串,我们记作$s \models t$。

对$2 \leq S < n$,令$G_S = (V, \Sigma, R, S)$表示$S$为初始符号的上下文无关文法,

  • 找到一个字符串$t \in L(G_S)$,使得对所有$1 \leq i \leq m$,$s_i \not\models t$;
  • 或者回答不存在这样的字符串。

约束:$|R| \leq 100, |s| = \sum_{i=1}^m |s_i| \leq 50$。其中,一个产生式$r$形如

$$r: a \to b_1 b_2 \dots b_k,$$

并记$|r| = k$。我们定义$|R| = \sum_{r \in R} |r|$。

解法:首先,我们将上下文无关文法$G$化为Chomsky范式,即每个转移$r$的长度$|r| \leq 2$。方法为,考虑转移$r: a \to b_1 b_2 \dots b_k$,其中$k \geq 3$,我们定义

$$
\begin{aligned}
a & \to b_1 c_1, \\
c_1 & \to b_2 c_2, \\
c_2 & \to b_3 c_3, \\
\dots \\
c_{k-3} & \to b_{k-2} c_{k-2}, \\
c_{k-2} & \to b_{k-1} b_k.
\end{aligned}
$$

这样转化后,转移式的规模仍为$O(|R|)$。以下则直接假设$|r| \in \{1, 2\}$。

接着,建立$m$个字符串$s_1, s_2, \dots, s_m$的AC自动机,则该自动机的状态集合为$\Gamma$,$|\Gamma| = O(|s|)$,并记$\downarrow$为其初始状态,$\delta: \Gamma \times \Sigma \to \Gamma$表示其转移函数。令$f(S, x, y)$表示符号$S$所能产生的所有字符串$L(G_S)$中的长度最小的字符串$t$的长度,使得$\delta(x, t) = y$且不经过接受状态。则我们要求$f(S, \downarrow, y)$,其中$y$不为接受状态。我们有

$$
f(S, x, y) = \min \begin{cases}
\min_u \{ f(b_1, x, u) + f(b_2, u, y) & S \to b_1b_2 \\
f(b_1, x, y) & S \to b_1
\end{cases},
$$

边界条件为对$a \in \{0, 1\}$,$f(a, x, y) = 1$若$\delta(x, a) = y$且$x$与$y$均不为接受状态。

状态数一共$O(|R||s|^2)$个,每轮迭代复杂度为$O(|R||s|^3)$,从而总复杂度为$O(|R|^2|s|^5)$,是不可接受的。

但我们仍可用堆优化,每次取出最小的$f(S, x, y)$扩展即可,而每个状态均摊扩展$O(|s|)$个新状态,从而复杂度为$O(|R||s|^3 \log(|R||s|^3))$。

代码:code

注:若限制堆中每个状态至多有$1$个最优扩展,则堆中至多有$O(|R||s|^2)$个元素,复杂度可降为$O(|R||s|^3 \log(|R||s|^2))$。

扩展Dijkstra

标签:最小值   使用   priority   get   ==   auto   理解   target   set   

原文地址:https://www.cnblogs.com/TinyWong/p/13638399.html

版权声明:完美者 发表于 2020-09-17 20:59:36。
转载请注明:扩展Dijkstra | 完美导航

暂无评论

暂无评论...