P1186tj

锦依卫小生 · 2023-10-15 21:19:05 · 题解

洛谷 P1186

题意分析

求出在删除任意一条边后从 1 号结点到 n 号结点的最短距离的最大值。

基本思想

不难分析出，要删除的边一定在在从 1 号结点到 n 号结点的最短路径上（否则最终结果仍然是删边前的最小值）。一种暴力的方法是先求出最短路，然后遍历一遍算出删除每一条边后的最短路径，取最大值——无法通过新增的 hack 数据。
不妨转换思路，最终删边后的路径一定经过至少一条删边前最短路径之外的边，那么可以考虑经过一条确定边的最短路径。推理论证后得出，假设该边两边结点编号位 u、v,d1、d2 数组分别表示到结点 1、n 的最短路径长度，那么经过边 u、v 的最短路 d1(u)+d2(v)+l_{uv}（l 表示边长），那么删除被这条路径“架空”的原最短路上的边的新最短路就可能是该值。
不难得出结论，从 u 出发回到 1 号结点的最短路径上最先到达的从 1 到 n 的最短路径上的结点（方便起见，我们称为父亲结点），与从 v 出发回到 n 号结点的最短路径上最先到达的从 n 到 1 的最短路径上的结点间的路径全部被架空。

本人采取边求最短路边求最先回到最短路径上的结点编号的方法（详见代码）。如此一来，题目就转化成了不断更新某一区间的路径被架空后的最小距离，最后查询每一条路径被架空后的最大值。很明显，可以使用线段树来实现。本篇题解采用标记下传。

具体做法与注意点

因为无法保证两边做 Dijkstra 求得的路径是一样的，本题解求最短路径只做一遍最短路，根据该条路径来确定关于 1 和 n 的父亲结点。 同时，也无法保证确定的父亲结点唯一，我们给最短路上的结点按照从 1 走到 n 标号，记为 rk。显然，为了结果最优，我们希望被架空的路径越多越好，那么求相对于 1 号结点的父亲结点时我们要做到等距离下 rk 越小越好，先对于 n 则反之。

如图，红色方案要优于蓝色方案
最后，关于线段树，要注意我们始终要维护 最小值，最后在枚举所有非最短路上的边后再遍历每一个元素求最大值。
总结起来，步骤如下：

• 求最短路大小与各个结点前驱。
• 根据前驱求出最短路径，并求出 rk。
• 再分别对 1 、 n 号结点求最短路，求出父亲结点。
• 枚举每一条非最短路径上的边，用线段树更新被其架空的路径段的最小值。
• 枚举每一条最短路径上的边，求出架空它们中的一个的最大值。

一些注意点和解释在注释中标明。时间复杂度 O(n^{2}\log{n})。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e3+5;
struct edge{
    int to,nxt,l;
};
edge e[MAX*MAX*2];
set<int> s;
int n,m,cnt=-1,head[MAX],d1[MAX],ans=0,d2[MAX],pre2[MAX][2],num;
int fa1[MAX],fa2[MAX],rk[MAX];
bool vis1[MAX],vis2[MAX],key[MAX];
int mins[MAX*4],swh[MAX*4];//swh 为 tag。
int read(){
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-'){
            f = -1;
        }
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}
void addedge(int u,int v,int x){
    cnt++;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].l=x;
    head[u]=cnt;    
}
void change(int k,int l,int r,int v){
    swh[k]=min(swh[k],v);
    mins[k]=min(mins[k],v);
}
void pushdown(int k,int l,int r){
    if(swh[k]>=1e9)
        return;
    int mid=l+r>>1;
    change(k<<1,l,mid,swh[k]);
    change(k<<1|1,mid+1,r,swh[k]);
    swh[k]=1e9;
}
int querry(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y)
        return mins[k];
    int mid=l+r>>1;
    pushdown(k,l,r);
    int res=2e9;
    if(x<=mid)
        res=min(res,querry(k<<1,l,mid,x,y));
    if(mid<y)
        res=min(res,querry(k<<1|1,mid+1,r,x,y));
    return res; 
}
void modify(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y)
        return change(k,l,r,v); 
    int mid=l+r>>1;
    pushdown(k,l,r);
    if(x<=mid)
        modify(k<<1,l,mid,x,y,v);
    if(mid<y)
        modify(k<<1|1,mid+1,r,x,y,v);
    mins[k]=min(mins[k<<1],mins[k<<1|1]);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        head[i]=-1;
    for(int i=1;i<=m;++i){
        int u,v,x;
        u=read();
        v=read();
        x=read();
        addedge(u,v,x);
        addedge(v,u,x);
    }

    memset(d1,0x3f,sizeof(d1));
    memset(d2,0x3f,sizeof(d2));

    d2[n]=0;
    for(int i=1;i<=n;++i){
        int t1=2e9,t2=0;
        for(int j=1;j<=n;++j){
            if(!vis2[j]&&d2[j]<t1){
                t1=d2[j];
                t2=j;
            }
        }
        vis2[t2]=1;
        if(t2==0)
            continue; 
        for(int j=head[t2];j!=-1;j=e[j].nxt){
            int v=e[j].to;
            if(!vis2[v]&&d2[v]>d2[t2]+e[j].l){
                d2[v]=d2[t2]+e[j].l;
                pre2[v][0]=t2;
                pre2[v][1]=j; 
            }
        }
    } //求出各个点到 n 的最短路径与它们的前驱。 

    int now=1;
    fa1[1]=1;
    fa2[1]=1;
    rk[1]=1;
    key[1]=1;
    while(now!=n){
        s.insert(pre2[now][1]);
        s.insert(pre2[now][1]^1);
        num++;
        now=pre2[now][0];
        rk[now]=num+1;
        key[now]=1;
        fa1[now]=now;
        fa2[now]=now;
    }//从 1 开始倒退求出最短路径，路径上结点的父亲等于他们自身。
     //同时求出 rk 即结点在路径中的顺序，同时把该边放入最短路集合，结点 key 赋值为 1。 

    d1[1]=0;//利用求最短路的过程求出父亲结点。
    for(int i=1;i<=n;++i){
        int t1=2e9,t2=0;
        for(int j=1;j<=n;++j){
            if(!vis1[j]&&d1[j]<t1){
                t1=d1[j];
                t2=j;
            }
        }
        if(t2==0)
            continue;
        vis1[t2]=1;
        for(int j=head[t2];j!=-1;j=e[j].nxt){
            int v=e[j].to;
            if(!vis1[v]&&d1[v]>d1[t2]+e[j].l){//如果 v 是通过 t2 更新的，那么 t2 是 v 的前驱，t2 的 v 的父亲。 
                d1[v]=d1[t2]+e[j].l;
                if(!key[v]){//最短路上的父亲不用更新。 
                    fa1[v]=fa1[t2];//类似并查集的操作，始终保证指向的是根结点，即最短路上的结点。 
                }
            }
            else
                if(d1[v]==d1[t2]+e[j].l&&!key[v]&&rk[fa1[t2]]<rk[fa1[v]]){//如果等距，则比较它们父亲的 rk。
                    fa1[v]=fa1[t2]; 
                } 
        }
    } 

    memset(d2,0x3f,sizeof(d2));//同样操作对 n 做一遍。
    memset(vis2,0,sizeof(vis2));
    d2[n]=0;
    for(int i=1;i<=n;++i){
        int t1=2e9,t2=0;
        for(int j=1;j<=n;++j){
            if(!vis2[j]&&d2[j]<t1){
                t1=d2[j];
                t2=j;
            }
        }
        vis2[t2]=1;
        if(t2==0)
            continue;
        for(int j=head[t2];j!=-1;j=e[j].nxt){
            int v=e[j].to;
            if(!vis2[v]&&d2[v]>d2[t2]+e[j].l){
                d2[v]=d2[t2]+e[j].l;
                if(!key[v]){
                    fa2[v]=fa2[t2];
                }
            }
            else
                if(d2[v]==d2[t2]+e[j].l&&!key[v]&&rk[fa2[t2]]>rk[fa2[v]]){
                    fa2[v]=fa2[t2];
                } 
        }
    } 

    memset(mins,0x3f,sizeof(mins));
    memset(swh,0x3f,sizeof(swh));
    for(int i=0;i<=cnt;++i){
        int u=e[i].to;
        int v=e[i^1].to;
        if(s.find(i)!=s.end())
            continue;//不能是最短路上的边。 
        int a=fa1[u];
        int b=fa2[v];
        if(rk[a]>=rk[b])
            continue; 
        int t=d1[u]+d2[v]+e[i].l;
        int l=rk[a];
        int r=rk[b]-1;
        if(l==0||r==0||l>r)
            continue;

        modify(1,1,num,l,r,t);
    }

    for(int i=1;i<=num;++i){
        int t=querry(1,1,num,i,i);
        ans=max(ans,t); //架空每一条路中的最大值。
    }

    cout<<ans;
}