【JSOI2015】地铁线路

Cry_For_theMoon · 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;
}