OI - 巴士走读(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 巴士走读(LOJ)

发表于 分类于 Valine：

本身题目不难，但是增广DP状态的思路比较重要

# 题面

> Linked LOJ 2872

点击展开/折叠 题面

有 $n$ 座城市，$m$ 班列车在其中穿行。

第 $i$ 辆列车在 $s_i$ 时刻从城市 $a_i$ 出发，在 $t_i$ 时刻到达 $b_i$；不记换乘的时间，这意味着如果 $b_i=a_j$ 且 $t_i=s_j$，你可以直接从 $i$ 换乘到 $j$。

进行 $Q$ 次询问，每次给出 $t$，询问“你从城市 $1$ 出发，在不晚于 $t$ 时刻到达城市 $n$，最晚要在什么时候第一次乘坐列车（可能无解）”。

$n,Q\le10^5,m\le3\times10^5$

# 解析

- 第一种思路

按照题目意思，直接定义 DP 状态 $f_u$ 表示要在 $t$ 时刻到达 $n$，则最晚要在什么时刻到达 $u$。

则 $f_n=t$，转移只需倒过来考虑——如果列车 $i$ 满足 $b_i=u$ 且 $t_i\le f_u$，则有可能在 $s_i$ 时刻在 $a_i$ 乘坐 $i$ 列车到达 $u$，那么最晚要在 $s_i$ 时刻到达 $a_i$。即 DP 转移

我们发现，当 $f_{b_i}$ 增大时，又新增了一些可以转移的车，那么不妨将询问离线下来从小到大排序，依次处理。

每次询问 $f_n$ 会增大，那么原本可以从 $n$ 转移出去的列车 $i$ 仍然可以转移；当 $f_n$ 增大超过 $b_i$ 时，$i$ 也可以转移了。由于是取 $\max$，显然对于任意 $u$，$f_u$ 只会增大不会减小，同理能从 $u$ 转移出去的列车也只会变多。

所以可以用增广的思想，将能够从 $u$ 转移出去的列车按 $t_i$ 排序，当 $f_u$ 增大到超过 $t_i$ 时，就用 $i$ 转移。这样，每辆列车只会被增广一次，复杂度 $O(m\log m)$（排序）。

简单地概括，这是一个从转移点实现增广DP的算法。

- 第二种思路

不那么直接，先对询问进行转化——新建虚拟城市 $n+1$，询问相当于在 $t$ 时刻有列车从 $n$ 出发到达 $n+1$，询问要坐上该列车，最少要什么时候从城市 1 出发。

定义 DP 状态：$f_u$ 表示要到达 $u$ 最晚要在什么时候出发，$g_i$ 表示要坐上第 $i$ 辆列车最晚要什么时候出发。

这样定义就意味着我们不需要考虑上了列车就要转移到下一个城市，而可以直接把列车看成两个节点——$s_i$ 时上车，$t_i$ 时下车。

转移边则变成有时间限制的转移：

  • 在 $s_i$ 时刻能从城市 $a_i$ 转移到列车 $i$；
  • 在 $t_i$ 时刻能从列车 $i$ 转移到城市 $b_i$；

于是把所有转移时间排序，然后依次处理转移。具体地说，现在枚举到时间节点 $t$，此时要进行的转移是：

  • 从列车 $i$ 到城市 $j$，则 $f_j:=\max\{f_j,g_i\}$；
  • 从城市 $i$ 到列车 $j$，若 $i=1$，则 $g_j:=t$；否则 $g_j:=\max\{g_j,f_i\}$；

注意应该先进行第一种转移，即先下车再上车，因为可以在一个城市下车后马上上另一辆车。

时间复杂度 $O(m\log m)$。

简单地概括就是从转移边实现的增广DP算法。

实际上两算法差别不大，第一种常数略小，因为如果 $f_u$ 没有办法增大到 $t_i$ 这么大，$i$ 就不会被转移。

我只写了第一种，另一种是同学写的%%%（当时我看得云里雾里的）

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+10;
#define ci const int &

struct DATA{
	int from,st,ed;
	DATA(){}
	DATA(ci F,ci S,ci E):from(F),st(S),ed(E){}
	inline friend bool operator <(const DATA &A,const DATA &B){
		return A.ed<B.ed;
	}
};

int n,m,Q;
int f[N],Tin[N],ans[N];
vector<DATA> Lin[N];
pair<int,int> qry[N];

inline int Read(int &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
void Aug(int u){
	while(Tin[u]<(int)Lin[u].size() && Lin[u][Tin[u]].ed<=f[u]){
		int v=Lin[u][Tin[u]].from;
		if(f[v]<Lin[u][Tin[u]].st){
			f[v]=Lin[u][Tin[u]].st;
			Aug(v);
		}
		Tin[u]++;
	}
}
int main(){
	Read(n),Read(m);
	for(int i=1,u,v,s,t;i<=m;i++){
		Read(u),Read(v),Read(s),Read(t);
		Lin[v].push_back(DATA(u,s,t));
	}
	for(int i=1;i<=n;i++) sort(Lin[i].begin(),Lin[i].end());
	Read(Q);
	for(int i=1;i<=Q;i++) Read(qry[i].first),qry[i].second=i;
	sort(qry+1,qry+1+Q);
	memset(f,-1,sizeof f);
	for(int i=1;i<=Q;i++){
		f[n]=qry[i].first;
		Aug(n);
		ans[qry[i].second]=f[1];
	}
	for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
	return 0;
}

THE END

Thanks for reading!

> Linked 云鸟-网易云