自动搬运

查看原文

来自洛谷，原作者为

	vegetable_ste 风波尽日依山转，星汉通霄向水悬。

搬运于2025-08-24 22:28:31，当前版本为作者最后更新于2021-08-09 21:09:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题解旨在更清晰地讲解分层图算法在此题的应用。

图1

4 3
1 2 3 2
101
011
110

对于这一组数据，如果 $\operatorname{O}(n^2)$ 暴力处理，显然会得到这样的图。

如何对其进行优化？

观察到 $k$ 较小，这种点的种类较少的题，分层图可以作为一个思考方向。

所谓分层，层与层之间维持有限制条件的联系，而层内部看作一个整体。

• 层内部的处理

观察式子 $|i - j|$ ，不难发现它的实质是一条边权为1的“链”上点 $i$ 和点 $j$ 之间的距离。因此，可以在层内部以 $(i, i + 1)$ 的方式连边。这里连无向边，因为一层是一个整体， $(i,j)$ 和 $(j, i)$ 的连通性、权值相同。

• 层之间的处理

把一层看作一个整体后，通过层与层之间不同点的关系维持题目当中 $S$ 的限制条件。

（第 $k$ 层的点 $u$ 记作 $\operatorname{get}(u, k)$ ）

考虑第 $1$ ~ $k$ 层对于第 $0$ 层的意义。第 $b[u]$ 层的点 $u$ 完全“继承”第 $0$ 层的点 $u$ 。 我们对第$0$层的点 $u$ 和 $\operatorname{get}(u, b[u])$ 连一条边权为0的有向边，把 $b[u]$ 层的所有点“固定”到点 $u$ 上。

然后，对于满足 $S_{k, b[u]} = 1$ 的所有组合，由 $\operatorname{get}(u, k)$ 向第 $0$ 层点 $u$ 连接有向边。

如果经过被“固定”到点 $u$ 的若干点又能从点 $\operatorname{get}(v, b[u])$ 回到第 $0$ 层点 $v$ ，那么就等同于建立了有向边 $(u, v)$ 。根据层内连边的规则，不难发现在第 $b[u]$ 层经过的边权之和即为 $|u - v|$ 。

这样，我们便巧妙地转化了 $S$ 所给出的限制条件。

可以借助图2理解。

图2

代码实现上 ，仍然将 $n$ 作为终点，所有非第 $0$ 层点都作为中间“过渡”点。

设置 $\operatorname{get}(u, k) = u + n \times k$ 作为由第 $0$ 层的 $u$ 跳转到第 $k$ 层对应点的标志。

P.S. 当一个图只含有边权为 $0, 1$ 的两种边的时候，可以用双端队列BFS进一步优化掉Dijkstra的一个 $\operatorname{log}$ （不过不用也没什么关系）

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define mp make_pair
const int N = 5e4 + 10, M = 52;
int n, k, b[N];
char s[M][M];
vector<PII> e[N * M];
int dist[N * M];
void Add(int x, int y, int w = 0, int f = 0) { e[x].push_back(mp(y, w)); if(f) e[y].push_back(mp(x, w)); }
#define get_l(x, t) ((x) + (t) * n) // 第t层点x的映射
void build() {
	// 1. 1至n层内部连边
	for(int i = 1; i <= k; i ++ )
		for(int j = 1; j <= n - 1; j ++ )
			Add(get_l(j, i), get_l(j + 1, i), 1, 1);
	// 2. 由第0层向其它层等效加边
	for(int i = 1; i <= n; i ++ ) Add(i, get_l(i, b[i]));
	// 3. 由其它层向第0层等效加边
	for(int i = 1; i <= k; i ++ )
		for(int j = 1; j <= n; j ++ )
			if(s[i][b[j]] == '1') Add(get_l(j, i), j);
}
void work() {
	#ifdef debug
	for(int i = 1; i <= get_l(n, k); i ++ ) {
		for_each(e[i].begin(), e[i].end(), [](PII x) -> void { cout << x.first << " "; });
		cout << endl;
	}
	#endif
	memset(dist, 0x3f, sizeof dist);
	deque<int> Q;
	Q.push_back(1); dist[1] = 0;
	while(!Q.empty()) {
		int t = Q.front(); Q.pop_front();
		for(unsigned i = 0; i < e[t].size(); i ++ ) {
			int u = e[t][i].first, w = e[t][i].second;
			if(dist[u] > dist[t] + w) {
				dist[u] = dist[t] + w;
				if(w) Q.push_back(u);
				else Q.push_front(u);
			}
		}
	}
	printf("%d\n", dist[n] > 1e9 ? -1 : dist[n]);
}
int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i ++ ) scanf("%d", b + i);
	for(int i = 1; i <= k; i ++ )
		scanf("%s", s[i] + 1); // 下标从1开始
	build();
	work();
	return 0;
}