自动搬运

查看原文

来自洛谷，原作者为

	zhuweiqi 攀峰之高险，岂有崖颠；搏海之明辉，何来彼岸？前进不止，奋斗不息。

搬运于2025-08-24 22:30:28，当前版本为作者最后更新于2023-08-29 16:16:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题的思路非常巧妙，是一道不可多得的带思维的广搜好题，下面我将循序渐进地教大家如何解决本题（特别地，在本篇题解中，所有变量均会统一用小写字母表示）。

一开始，我粗略地看完题目之后，脑海中冒出来的第一个想法是跑 $p$ 遍单源最短路，由于路径权值只有 $0$ 和 $1$，因此可以简化成一个关于 bfs 的问题，每次扩展的范围就是所有经过当前车站的线路停靠的所有站点，对于每个询问，如果车站 $s$ 能扩展到车站 $t$，就让 $ans$ 加上对应的贡献值， 最后输出 $ans$。我花了 $20$ 分钟时间将我这个想法成功地实现了出来：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;
	char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0' && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x;
}
const int N=100002,M=1002;
vector<int> line[M];
vector<int> station[N];
int f[N];
queue<int> q;
void bfs(){
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(auto l:station[x]){
			for(auto s:line[l]){
				if(f[s]==-1){
					f[s]=f[x]+1;
					q.push(s);
				}
			}
		}
	}
	return;
}
int main(){
	int n=read(),m=read(),p=read(),k,x,s,t,ans=0;
	for(int i=1;i<=m;i++){
		k=read();
		while(k--){
			x=read();
			line[i].push_back(x);
			station[x].push_back(i);
		}
	}
	while(p--){
		s=read(),t=read();
		memset(f,-1,sizeof(f));
		q.push(s);
		f[s]=0;
		bfs();
		if(f[t]!=-1) ans+=f[t];
	}
	printf("%d",ans);
	return 0;
}

Unfortunately，T 飞了。

仔细地分析了一下这个代码的时间复杂度，发现最坏情况下竟然是 $O(pn^2)$ 的。很显然，这个时间复杂度级别的代码无论怎么优化都不可能卡过去。

此时，我们就需要改变解决本题的思路。我们在数据范围内发现到一个很奇怪的东西，每个车站停靠的线路数量不超过 $50$，然后再结合着 $m\leq 1000$ 一起看，我们是否能将主要的时间复杂度转移到 $m$ 上去呢？继续深入地思考一下，我们发现刚才的那个 bfs 貌似是按照地铁线路，一个一个车站地去扩展的，诶？那我们为什么不把车站放一边，直接按照地铁线路去扩展呢？

至此，正解大致的思路已经出来了，首先我们用一个邻接矩阵存储两条线路之间是否有共同停靠的站点，接着把邻接矩阵用邻接表存储节约之后 bfs 的时间，然后预处理 $dis$ 数组（$dis_{i,j}$ 表示从第 $i$ 条线路到第 $j$ 条线路至少需要换乘几次，注意，需要初始化整个数组为一个小于 $0$ 的值，并且要把 $dis_{i,i}$ 的值初始化为 $0$），这个过程可以通过 $n$ 遍 bfs 来实现，最后，对于每个询问，枚举第一条线路和最后一条线路（即枚举停靠车站 $s$ 和车站 $t$ 的线路），输出贡献值的总和即可，设 $a$ 为 $siz_i$ 中的最大值，则时间复杂度最坏情况下为 $O(m^2+a^2n)$，可以通过本题（link）！参考代码如下：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;
	char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0' && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x;
}
const int N=100002,M=1002,inf=1e9;
vector<int> station[N];
bool con[M][M];
vector<int> c[M];
int dis[M][M];
queue<int> q;
void bfs(int st){
	dis[st][st]=0;
	q.push(st);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(auto y:c[x]){
			if(dis[st][y]==-1){
				dis[st][y]=dis[st][x]+1;
				q.push(y);
			}
		}
	}
	return;
}
int main(){
	int n=read(),m=read(),p=read(),k,x,s,t,ans=0;
	for(int i=1;i<=m;i++){
		k=read();
		while(k--){
			x=read();
			station[x].push_back(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(auto u:station[i]){
			for(auto v:station[i]){
				con[u][v]=con[v][u]=1;
			}
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if(con[i][j]){
				c[i].push_back(j);
			}
		}
	}
	memset(dis,-1,sizeof(dis));
	for(int i=1;i<=m;i++) bfs(i);
	while(p--){
		s=read(),t=read();
		int mins=inf;
		for(auto u:station[s]){
			for(auto v:station[t]){
				if(dis[u][v]!=-1){
					mins=min(mins,dis[u][v]+1);
				}
			}
		}
		if(mins!=inf) ans+=mins;
	}
	printf("%d",ans);
	return 0;
}