P10053 题解

寻逍遥2006 · 2024-01-05 17:54:48 · 题解

简要题意：一天有 S 个时刻。有 Q 个人，其中第 i 个人要从 T_i 时刻开始从 U_i 走到 V_i。对于每条边 (A_i,B_i) 经过它需要 L_i 的时间，它会在第 C_i 个时刻关闭，这也就意味着只有在每天的前 C_i-L_i 个时刻才能够走上这条路。问每个人至少需要多长的时间能够到达目的地。

首先答案必然有一个上界 S\times n-T_i，也就是把第一天等完，然后一天走一条边。

我们考虑一个人可能走的两种情况：

1. 在一天之内完成了整个路程。
2. 用至少两天完成了整个路程。

第二种情况

对于第二种情况，我们可以将其分解成三段：第一天，中间的若干天（可能没有），最后一天。我们逐个来考虑。

第一天

考虑路径 U\to V。我们可以倒过来看：初始权值为 S，从 V 点走到 U 点，经过了第 i 条边，权值会变成 \min(S,C_i)-L_i，我们要最大化最后的权值。

这个过程类似最短路可以使用 Dijkstra 实现，以每一个点为起点跑一遍，时间复杂度 O(nm\log m)。由于这个图是稠密图，所以 Dijkstra 单次可以做到 O(n^3)。

最后一天

考虑路径 U\to V。这个和正常的最短路是类似的，但是只有转移权值 \le C_i-L_i 才能沿着第 i 条边转移。

这个也可以使用 Dijkstra 实现，以每一个点为起点跑一遍，时间复杂度 O(nm\log m) 或者 O(n^3)。

中间的若干天

每一天都可以看作是一条和“最后一天”相同的路径，利用最后一天对应的数组来生成一张图：如果可以从 U 到达 V，则我们加入一条 U\to V 的权值为 S 的边。

然后在这张图上跑 Floyd 即可，时间复杂度 O(n^3)。

考虑如何计算对于答案的贡献，一个很暴力的想法是枚举第一天的终点 U' 和最后一天的起点 V'，判断第一天 U\to U' 的合法性，然后把三段的贡献加到一起。但是这样单次的复杂度为 O(n^2) 无法接受。

我们考虑到 V' 的枚举是只与 U' 和 V_i 有关的，与 U_i 和 T_i 无关。所以我们预处理对于每一个 U' 和 V_i 的 V' 的枚举，这样在求解的过程中只需要枚举 U' 即可。单次求解时间复杂度为 O(n)。

第一种情况

我们考虑一条从 T=0 时刻开始的，合法的从 U 到 V 的路径，每次必然是能走就走，我们逐渐的增大 T，直到某一个时刻 T=T'+1 时，有一条路是不可经过的了。也就是至多在 T' 时刻出发，才能够走这一条路径。我们考虑限制住这条路径的是编号为 x 的边，则从 T' 时刻出发，必然会在 C_x-L_x 时刻到达 A_x 或 B_x，再在 C_x 时刻到达这条边的另一端。

我们考虑枚举这条边 x，则可以将所有这样的路径拆成两部分（假设从 A_x 进入这条边，从 B_x 离开这条边，反过来也是类似的）：第一部分是从 U\to A_x，在 C_x-L_x 时刻到达 A_x，这个可以和第二种情况中的“第一天”类似的方式处理；第二部分是 B_x\to V，从 C_x 时刻出发，这个可以和第二种情况中的“最后一天”类似的方式处理。

对于某一对 U,V，假设我们得到至多在 T_1 时刻从 U 出发，可以在 T_2 时刻到达 V，则如果要走 U\to V，且可以在 \le T_1 的时刻出发，就可以以 T_2-T_1 的代价走到。

对于每一对 U,V，都可以得到这样的 O(m) 条路径，将其按照 T_1 排序，去掉所有被其他路径偏序了的路径，就可以通过一次二分来得到每一次询问能否在第一天之内到达，同时可以得到它需要消耗的最短时间。

考虑时间复杂度：对于枚举每一条边跑一次 Dijkstra，时间复杂度为 O(mn^2)；对于每一个 U\to V 点对处理那 O(m) 条路经，时间复杂度 O(n^2m\log m)；每一次求解答案需要一次二分，时间复杂度 O(Q\log m)。

总体时间复杂度为 O(n^2m\log m+Q(n+\log m)) 可以通过。

#include "escape_route.h"
#include <bits/stdc++.h>

using namespace std;

template<typename T>bool get_max(T &a,T b){if(a<b) return a=b,true;return false;}
template<typename T>bool get_min(T &a,T b){if(a>b) return a=b,true;return false;}

vector<long long> ans;
vector<pair<int,int> >ed[100];
vector<pair<long long,long long> >mind[100][100],tmp;
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > G;
priority_queue<pair<long long,int> >G_;
long long dis[100][100],tr[100][100];

long long sid[100][100];

long long dis1[100],dis2[100];

int f[100][100];
bool vis[100];

vector<long long> calculate_necessary_time(
    int N, int M, long long S, int Q, vector<int> A, vector<int> B,
    vector<long long> L, vector<long long> C, vector<int> U,
    vector<int> V, vector<long long> T)
{
    ans.resize(Q);
    for(int i=0;i<M;i++)
        ed[A[i]].push_back(make_pair(B[i],i)),
        ed[B[i]].push_back(make_pair(A[i],i));

    //solve go in days

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++) dis[i][j]=S*N,vis[j]=false;
        dis[i][i]=0;G.push(make_pair(0ll,i));
        while(!G.empty())
        {
            int v=G.top().second;G.pop();
            if(vis[v]) continue;
            vis[v]=true;
            for(pair<int,int> g:ed[v])
                if(dis[i][v]+L[g.second]<=C[g.second]&&dis[i][g.first]>dis[i][v]+L[g.second])
                    G.push(make_pair(dis[i][g.first]=dis[i][v]+L[g.second],g.first));
        }
        for(int j=0;j<N;j++)
            f[i][j]=(dis[i][j]<S?1:N+1);
    }
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++) sid[i][j]=-1,vis[j]=false;
        sid[i][i]=S;G_.push(make_pair(S,i));
        while(!G_.empty())
        {
            int v=G_.top().second;G_.pop();
            if(vis[v]) continue;
            vis[v]=true;
            for(pair<int,int> g:ed[v])
                if(get_max(sid[i][g.first],min(sid[i][v],C[g.second])-L[g.second]))
                    G_.push(make_pair(sid[i][g.first],g.first));
        }
    }

    for(int i=0;i<N;i++)
        f[i][i]=0;

    for(int k=0;k<N;k++)
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
        f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
    {
        tr[i][j]=f[i][j]*S;
        for(int k=0;k<N;k++)
            tr[i][j]=min(tr[i][j],f[i][k]*S+dis[k][j]);
    }

    //solve go in one day

    for(int i=0;i<M;i++)
    {
        //A[i]->B[i]
        memset(dis1,0xcf,sizeof(dis1));
        memset(dis2,0x3f,sizeof(dis2));
        dis1[A[i]]=C[i]-L[i],dis2[B[i]]=C[i];
        memset(vis,0,sizeof(vis));
        for(int j=0,mx;j<N;j++)
        {
            mx=-1;
            for(int k=0;k<N;k++)
                if(!vis[k]&&(mx==-1||dis1[mx]<dis1[k]))
                    mx=k;
            vis[mx]=true;
            for(pair<int,int> g:ed[mx])
                if(dis1[mx]<=C[g.second]&&dis1[g.first]<dis1[mx]-L[g.second])
                    dis1[g.first]=dis1[mx]-L[g.second];
        }
        memset(vis,0,sizeof(vis));
        for(int j=0,mn;j<N;j++)
        {
            mn=-1;
            for(int k=0;k<N;k++)
                if(!vis[k]&&(mn==-1||dis2[mn]>dis2[k]))
                    mn=k;
            vis[mn]=true;
            for(pair<int,int> g:ed[mn])
                if(dis2[mn]<=C[g.second]-L[g.second]&&dis2[g.first]>dis2[mn]+L[g.second])
                    dis2[g.first]=dis2[mn]+L[g.second];
        }
        for(int x=0;x<N;x++)
        for(int y=0;y<N;y++)
            if(dis1[x]>=0&&dis2[y]<=S)
                mind[x][y].push_back(make_pair(dis1[x],dis2[y]-dis1[x]));

        //B[i]->A[i]
        memset(dis1,0xcf,sizeof(dis1));
        memset(dis2,0x3f,sizeof(dis2));
        dis1[B[i]]=C[i]-L[i],dis2[A[i]]=C[i];
        memset(vis,0,sizeof(vis));
        for(int j=0,mx;j<N;j++)
        {
            mx=-1;
            for(int k=0;k<N;k++)
                if(!vis[k]&&(mx==-1||dis1[mx]<dis1[k]))
                    mx=k;
            vis[mx]=true;
            for(pair<int,int> g:ed[mx])
                if(dis1[mx]<=C[g.second]&&dis1[g.first]<dis1[mx]-L[g.second])
                    dis1[g.first]=dis1[mx]-L[g.second];
        }
        memset(vis,0,sizeof(vis));
        for(int j=0,mn;j<N;j++)
        {
            mn=-1;
            for(int k=0;k<N;k++)
                if(!vis[k]&&(mn==-1||dis2[mn]>dis2[k]))
                    mn=k;
            vis[mn]=true;
            for(pair<int,int> g:ed[mn])
                if(dis2[mn]<=C[g.second]-L[g.second]&&dis2[g.first]>dis2[mn]+L[g.second])
                    dis2[g.first]=dis2[mn]+L[g.second];
        }
        for(int x=0;x<N;x++)
        for(int y=0;y<N;y++)
            if(dis1[x]>=0&&dis2[y]<=S)
                mind[x][y].push_back(make_pair(dis1[x],dis2[y]-dis1[x]));
    }

    for(int x=0;x<N;x++)
    for(int y=0;y<N;y++)
    if(mind[x][y].size())
    {
        sort(mind[x][y].begin(),mind[x][y].end(),[&](pair<long long,long long> A,pair<long long,long long> B)
        {if(A.first!=B.first) return A.first<B.first;else return A.second>B.second;});
        vector<pair<long long,long long> >().swap(tmp);
        for(pair<long long,long long> &g:mind[x][y])
        {
            while(!tmp.empty()&&tmp.rbegin()->second>g.second) tmp.pop_back();
            tmp.push_back(g);
        }
        swap(tmp,mind[x][y]);
    }

    vector<pair<long long,long long> >::iterator it;

    for(int i=0;i<Q;i++)
    {
        if((it=lower_bound(mind[U[i]][V[i]].begin(),mind[U[i]][V[i]].end(),make_pair(T[i],0ll)))!=mind[U[i]][V[i]].end())
            ans[i]=it->second;
        else ans[i]=(N+1)*S;

        if(T[i]<=sid[V[i]][U[i]])
            get_min(ans[i],S-sid[V[i]][U[i]]);

        for(int j=0;j<N;j++)
            if(T[i]<=sid[j][U[i]])
                get_min(ans[i],S-T[i]+tr[j][V[i]]);
    }
    return ans;
}

注：需要写标准输入输出，而不是 JOISC 的交互。