2021-04-29 17:18 已编辑华南农业大学全栈开发

关注

2021年4月15日题目 [JSOI2015]地铁线路

[JSOI2015]地铁线路

https://ac.nowcoder.com/acm/problem/20214

题号 NC20214
名称 [JSOI2015]地铁线路
来源 [JSOI2015]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

JSOI王国的地铁又涨价了！正在JSOI旅游的JYY非常不开心L。这次票价改革后，乘客并不是按照乘坐的距离收费，而是按照换乘次数进行收费的！JYY 也要按此更新他的线路搜索软件了。 JYY心想，在支付同样票价的前提下，岂不是坐的站数越多，自己就赚的越多嘛！于是JYY希望开发一个线路搜索软件，使得自己总能够“赚”的最多！

JSOI地铁一共有N条线路S个车站。第i条地铁线路包含Li个站。所有地铁线路都是一条从首发站到终点站的直线型线路（不存在例如北京地铁2号线或者 10号线那样奇葩的环线）。同时，每一条地铁线路都是双向运行的。如果有不同的线路经过同一个地铁站，那么乘客就可以在那个地铁站进行换乘。根据JSOI地铁的最新收费方式，每当乘客进入一列正在运行的地铁列车，都需要支付1的费用。因此，假设乘客一共换乘了x次，那么就需要总共支付x+1的乘车费用。

由于地铁线路都是双向运行的，因此在任意一站都可以换乘该线地铁反方向运行的列车。不过，需要注意的是，即使是换乘同样线路的反方向列车，也是需要付费的（因为总是需要先下车，再重新上车的）。 JYY现在要从A站坐地铁前往B站。假设对于任意一条地铁线路，相邻两站间地铁的运行时间均为1分钟，并且列车停站和换乘均不耗时间，JYY想知道

1)他最少需要支付的票价是多少钱；

2)在支付最少票价的前提下，他最多可以乘坐多少分钟的地铁。

样例

示例1
输入
2 5 
A B C D E 
4 A B C D 
3 C D E 
A D
输出
1
3

$2 \leq N \leq 4 \times 10^5,S\leq 3\times 10^5 ,\sum L_i\leq 8\times 10^5$

算法

(最短路 + 建图 + 动态规划)

建图

如果按照题意暴力的拆点建边很容易超过内存限制，所以本题的重点在于如何建图

对于不同路线中的同一个站点我们不需要将它拆成多分，

我们只需要对于每一条路线建立一个虚拟节点 $line[i]$ ,表示代表第 $i$ 条路线的虚拟节点

**然后对于第 $i$ 条路线上的所有站点向 $line[i]$ 连一条边权为 $1$ 的有向边**

从某一个点，如A经过边权为1的边进入虚拟节点i，表示从站点A离开点前路线进入路线i

然后从 $line[i]$ 向第 $i$ 条路线上的所有站点连一条边权为 $0$ 的有向边

从虚拟节点i经过边权为0的边进入某个节点，如A，表示从路线i经过一系列的站点（可以是0个站点）到达站点A（方向不需要我们考虑但一定是单向的）

整个图大致的样子如下图

图片说明

深蓝色圈表示站点，红色圈表示路线的虚拟节点，绿边边权为1，黄边边权为0

这样建边的空间复杂度是 $O(2\sum_iL_i)的$

求小花费

我们发现图中只有边权为1和0的边所以我们可以用01bfs求解

进行完 $01bfs$ 后我们就知道到达所有站点（包括路线）的最小花费 $dist[i]$ 是多少了

求最大乘坐时间

由于我们首先需要满足最小花费后再来满足最长的乘坐时间

所以答案一定是在一个从起点走到终点的最小花费路径（最短路图）上求解的

最短路图必定是一个有向无环图所以我们可以使用动态规划

但这一题不需要真的建一个最短路图

由于每一条路线的最小花费是确定的所以我们可以将所有路线按照最小花费 $dist$ 从小到大排序

在这个序列中就可以进行动态规划

状态表示: $f[i]$ 表示当前到达点 $i$ 的最大乘坐时间

状态计算:我们考虑到达站点i的上一个位置是哪里

我们可能是从另一条路线经过站点j转站到当前路线

所以 $dist[j] == dist[i] - 1$ ,我们有 $f[i] = max(f[i],f[j])$
如果此时是站内转移，那么有两种情况
1. 沿着正方向移动坐到i
2. 沿着反方向移动到坐到i
站内转移的情况我们可以看成是一个序列问题所以我们可以维护一个最大的前缀和后缀进行状态转移

$f[i] = max(f[i],max(pre[i],suf[i]))$ ( $pre[i]为最大前缀，suf[i]为最大后缀$ )
```
细节见代码注释
```
时间复杂度 $O(N + (N + S))$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <deque>

using namespace std;
typedef pair<int,int> PII;
const int N = 400010,M = 2400010,INF = 0x3f3f3f3f;
vector<PII> lines;
int st[N];
int h[N],ne[M],e[M],w[M],idx;
int h1[N],d[N];
int n,m;
char station[50];
unordered_map<string,int> id;
int pre[N],suf[N];
int dist[N];
int f[N];
int cnt;
int S,T;

void add(int h[],int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

void bfs()
{
    memset(dist,-1,sizeof dist);
    deque<int> q;
    q.push_front(S);
    dist[S] = 0;
    while(q.size())
    {
        int t = q.front();
        q.pop_front();
        for(int i = h[t];~i;i = ne[i])
        {
            int j = e[i];
            if(dist[j] == -1)
            {
                dist[j] = dist[t] + w[i];
                if(w[i] == 1) q.push_back(j);
                else q.push_front(j);
                add(h1,t,j,w[i]);
                d[j] ++;
            }
        }
    }
}

void topsort()
{
    int q[N],hh = 0,tt = -1;
    for(int i = 1;i <= n + m;i ++)
        if(!d[i])
            q[++ tt] = i;
    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h1[t];~i;i = ne[i])
        {
            int j = e[i];
            d[j] --;
            if(!d[j]) q[++ tt] = j;
            if(dist[j] )
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    memset(h1,-1,sizeof h1);
    for(int i = 1;i <= m;i ++) 
    {
        scanf("%s",station);
        if(!id.count(station)) id[station] = ++ cnt;
    }
    for(int i = 1;i <= n;i ++)
    {
        int l;
        scanf("%d",&l);
        while(l --)
        {
            scanf("%s",station);
            add(h,id[station],i + m,1);
            add(h,i + m,id[station],0);
        }
    }
    scanf("%s",station);
    S = id[station];
    scanf("%s",station);
    T = id[station];
    bfs();
    if(dist[T] == INF)//到达不了
    {
        printf("-1\n0\n");
        return 0;
    }
    for(int i = 1;i <= n;i ++)
        lines.push_back(make_pair(dist[i + m],i + m));
    sort(lines.begin(),lines.end());
    int r = 0;
    while(r < lines.size() && lines[r].first <= 0) r ++;
    for(int i = 1;i <= n;i ++)
    {
        int l = r;
        while(r < lines.size() && lines[r].first == i) r ++;
        for(int j = l;j < r;j ++)
        {
            int x = lines[j].second;
            int len = 0;
            for(int u = h[x];~u;u = ne[u])
                st[++ len] = e[u];//把当前路线的站点按顺序转化成序列
            pre[0] = suf[len + 1] = -INF;
            for(int k = 0;k <= len - 1;k ++)//从上一条路线转移,并且维护前缀最大值
            {
                int s = st[k + 1];
                pre[k + 1] = pre[k] + 1;
                if(dist[s] == i - 1) pre[k + 1] = max(pre[k + 1],f[s]);
            }
            for(int k = len + 1;k > 0;k --)//从上一条路线转移，并且维护后缀最大值
            {
                int s = st[k - 1];
                suf[k - 1] = suf[k] + 1;
                if(dist[s] == i - 1) suf[k - 1] = max(suf[k - 1],f[s]);
            }
            for(int k = 1;k <= len;k ++)
            {
                int s = st[k];
                if(dist[s] == i) f[s] = max(f[s],max(pre[k],suf[k]));//同一条路线转移
            }
        }
    }
    printf("%d\n",dist[T]);
    printf("%d\n",f[T]);
    return 0;
}