自动搬运

查看原文

来自洛谷，原作者为

	Cry_For_theMoon **

搬运于2025-08-24 22:17:22，当前版本为作者最后更新于2020-10-29 19:45:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

  传送门

  图论建模优秀题。解法其实很巧妙，但是切掉一道题后只有深入思考是如何想到这个做法的，这道题目才是真正有意义的

  考虑处理线路，同一线路上的所有点花费1代价相互可达，我们不可能对每个点去和与他同一线路上的点连边，因为 $\sum l_i <= 8*10^5$，也就是意味着边数可能到达 $64*10^{10}$，考虑你选两个点，它们其实会和剩下的点都连一条边，也就是说一条线路里会有很多个站连一个相同的站，考虑把所有连接 $i$ 的边合并成一条边，但是它们终点相同却又起点不同，因此我们开一个“虚点”，所有点去连这个虚点，边权为1，虚点和所有的该线路上的点（边权为0）相连就可以了。看上去对于每个点都要开一个对应的虚点？然而我们发现每个虚点都被该线路所有点相连，也连接该线路所有点，我们还可以把这些虚点合并成一个。此时就满足了同一线路上所有点花费1代价相互可达的题意。

  对于第一问，显然就是最短路。考虑 $i$ 的上一个点 $j$ 满足 $dis_j=dis_i-1$ 的点转移（因为你要从点 $j$ 上地铁花费1），排序后 DP（这个倒不难想，做过图上DP类的（比如逛公园，大陆争霸）都应该明白），而且这里没有等于号方便了很多。这个柿子显然意味着 $i,j$ 位于同一条地铁上，所以一个点只会被和他在同一个地铁上且 $dis$ 比他少1的点转移，这个柿子又意味着这条地铁的虚点的最短路 = 点 $i$ 的最短路，所以其实我们对 $n$ 个虚点排序，然后铁路上转移所有最短路 = 虚点最短路的点即可。

  此时分两种情况，转移点在当前点之前/之后，我们只分析之前（之后的分析是一样的），设当前点是 $i$，你维护的是 $1..i-1$ 站中满足 $dis_j = dis_i-1$ 且 $f(j)+i-j$ 最大的 $j$，如果你学过多重背包优化单调队列这种，你就会立刻发现不管 $j$ 选什么 $+i$ 都不变，因此维护的其实是 $1..i-1$ 中 $f(j)-j$ 最大的，这个柿子是独立的，这样的话每个点的转移就都是 $O(1)$ 的，又因为所有铁路的点数之和 $L<=8e5$，所以DP这里 $O(L)$ 时间复杂度完全可以跑的飞快（主要复杂度还是在最短路那里，我写了Dij，写BFS可以快一点）

  在一开始的建图中，我和 M_sea 神仙的方法是一样的。事实上根据我们刚才的分析，完全可以改成“所有点去练虚点的边权为0，虚点连所有点的边权为1”（即反一下），然后DP的时候其实是转移铁路上所有最短路=虚点最短路+1的点，而上文中 $j$ 的条件也变成了点 $j$ 的最短路和虚点最短路相等。你可以把开始的方法看作花钱上地铁然后下地铁不要钱，这种建图方法看成先上车下车补票，本质上是没有任何区别的。如果你看懂了前面的内容，这里应该是一下反应过来的。

  虽然这题DP是重头戏但是这题DP做法我觉得带给我们的帮助其实并不是很大，反而是建图方法值得好好揣摩。

  但是我知道你们都只会看Code的

//JSOI,2015
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<string>
using namespace std;
const int MAXN=4e5+10,MAXM=2e6+10,INF=1e9;
struct Edge{
	int u,v,w;
};
struct Node{
	int u,dis;
	bool operator<(const Node& n2)const{
		return dis > n2.dis;
	}
};
struct Line{
	int u,d;
	bool operator<(const Line& n2)const{
		return d < n2.d; 
	} 
}Lines[MAXN];
map<string,int>fs;
Edge edge[MAXM];
int first[MAXN],next[MAXM],tot;
int dis[MAXN],vis[MAXN],f[MAXN],point[MAXN];
int lines,n;
inline void addedge(int u,int v,int w){
	edge[++tot].u=u;edge[tot].v=v;edge[tot].w=w;
	next[tot]=first[u];first[u]=tot;
}
inline int getstation(int u){
	return u+n;
}
void dijkstra(int s){
	for(int i=1;i<=lines+n;i++){
		dis[i] = INF;
	}
	dis[s] = 0;
	priority_queue<Node>h;h.push((Node){s,0});
	while(!h.empty()){
		Node now = h.top();h.pop();
		int u = now.u;
		if(vis[u])continue;
		vis[u] = 1;
		for(int j=first[u];j;j=next[j]){
			int v = edge[j].v;
			if(dis[v] > dis[u]+edge[j].w){
				dis[v] = dis[u]+edge[j].w;
				h.push((Node){v,dis[v]});
			}
		}
	}
}
int main(){
	scanf("%d%d",&lines,&n);
	string tmpname;
	for(int i=1;i<=n;i++){
		cin>>tmpname;fs[tmpname]=i;
	}
	for(int i=1,l;i<=lines;i++){
		scanf("%d",&l);
		for(int j=1;j<=l;j++){
			cin>>tmpname;
			int u = getstation(i),v = fs[tmpname];
			addedge(v,u,0);//上车
			addedge(u,v,1);//下车 
		}
	}
	string startname,endname;
	cin>>startname>>endname;
	int s = fs[startname],e = fs[endname];
	dijkstra(s);
	if(dis[e]==INF){
		printf("-1\n0");return 0;
	}
	printf("%d\n",dis[e]);
	for(int i=1;i<=lines;i++){
		Lines[i] = (Line){getstation(i),dis[getstation(i)]};
	}
	sort(Lines+1,Lines+1+lines);
	for(int i=1;i<=n;i++)f[i]=-INF;
	f[s]=0;
	for(int i=1;i<=lines;i++){
		int u = Lines[i].u;
		if(dis[u]==INF)break;
		int rear = 0;
		for(int j=first[u];j;j=next[j]){
			int v = edge[j].v;
			point[++rear] = v;
		}
		int maxn = 0;
		for(int j=1;j<=rear;j++){
			int v = point[j];
			if(dis[v]==dis[u]+1){
				if(maxn!=0){
					f[v] = max(f[v],f[point[maxn]]+j-maxn);
				}
			}else if(dis[v]==dis[u]){
				if(maxn){
					if(f[point[maxn]]-maxn < f[point[j]]-j)maxn=j;
				}else{
					maxn=j;
				}
			}
		}
		maxn = 0;
		//转移前缀 
		for(int j=rear;j>=1;j--){
			int v = point[j];
			if(dis[v]==dis[u]+1){
				if(maxn!=0){
					f[v] = max(f[v],f[point[maxn]]+maxn-j);
				}
			}else if(dis[v]==dis[u]){
				if(maxn){
					if(f[point[maxn]]+maxn < f[point[j]]+j)maxn=j;
				}else{
					maxn=j;
				}
			}
		}
	}
	printf("%d",f[e]);
	return 0;
}