题解 P3238 【[HNOI2014]道路堵塞】

· · 题解

由于题解很少加上讲解都好精炼，蒟蒻琢磨了好久，于是贡献一片题解

（前方多图预警）

题面传送门

博客体验应该不会更佳

1.化简题意

在有向正边权图中，给出 1 到 n 最短路径经过的边，求每删除有且只有一条边后的最短路

2.寻找解法

从题意上我们得不到直观的求解方式或思路（仅提供最短路这一思考方向），那我们就寻找题目性质

首先模拟题意，接下来是探索性质的思考过程，以图片形式呈现，各位大佬可以选择阅读或自行探究，结论探讨总结会在4幅图后呈现

探索开始

原图（最短路用红色表明，题目已知）

断开第一条边（紫色为答案，绿色为可行解，下面同理）

断开第二条边

断开第三条边

探索结束

结论开始

（由于图片展示有限，各位大佬可以模拟更长的路径，可以得到同样的结论）

咦，我们发现答案的边都是在最短路上跑一点，然后跳出来，又回到最短路也！

那是不是就是这个性质呢？

首先，我们先大胆猜想，然后再简单证明

（绿色为答案路径，紫色为非答案路径）

那不能够走紫色这条边吗？

显然，如果我们走路径k，那么对于最短路i到j，就会有更优解路径k来代替原来的路径，那路径k就成了最短路了

显然这与题意不符

可是真的只会绕一个弯吗？

显然题目要求我们只断一条边，所以即便是绕路，也只用绕一个弯，绕多个弯就不优了，这个可以结合上面的证明感性理解。

所以我们就得到性质：

对于答案路径，一定是在原最短路上走一段路，然后从最短路上一点绕开断路，走到最短路上另一点，再继续走最短路，回到终点。

如图所示

形式化的：

\text{对于} edge_{i-j},\text{答案路径为}1-x_u-x_v-n \text{其中}x_u<i,x_v>j,\text{且}1-x_u,x_v-n\text{属于原最短路径},x_u-x_v\text{不属于原最短路径且使答案最优}

注意此时的大于和小于是指我们对最短路上的点编号后的结果

3.解法实现

说了这么多性质，到底如何实现呢？？？

显然我们不可能对每一条边断开后单独求解

那我们就考虑是不是答案有传递性，相互之间的贡献，或者任何共同性可以减少复杂度的

那我们的性质就要派上用场了 （废话

我们发现，我们的绕路都是从一个地方跳出来，然后再回去

从1-n的顺序遍历，如果前面的路径也绕开了这条边，我们是不是就可以使用呢？

显然，之前的答案对于现在是有贡献的，但是不一定是最优的

所以我们是不是还要从这条断边的起点SPFA一次，获得这个点对答案（也就是绕开路径）的贡献

那答案是否有有限的贡献范围呢？

显然，如果这一条远路没有绕开断边，对后面的答案都没有贡献了

所以绕远路的终点，也就是回到最短路上的点，需要比现在的断边的终点大

然后我们又发现，断边的枚举是递增的

每次插入一个比现在大的点和权值，然后寻找最小的权值且满足要求

动态维护一个最小值，支持删除插入，时间复杂度在O(log\space n)左右，我们就可以突发奇想，想到小根堆！

接下来整理解法

由于这里找到最短路上的点后需要快速得到到终点的长度，并插入堆

所以预处理一个到终点的最短路值，同时减少没有必要的尝试，减少时间

其实就是这幅图啦

4.时间复杂度简析

蒟蒻只会简单分析，有错请指正

设最短路上有n_1个点，不在最短路上有n_2个点

枚举断边O(n_1)

每一个断边最坏需要O(n_2\space m)

那复杂度就需要O(n_1\space n_2\space m)

还有一个堆的复杂度O(log n_1)

貌似很大，但是每一次拓展，堆理论的大小都会减小，SPFA的拓展也越来越有限，而且这理论上是一个稀疏图

综上，复杂度为O(\text{玄学能过})

只要常数好，就卡得过

所以这是一段瞎扯

5.代码

还是这个最重要

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read()//蒟蒻不太会快读（雾）
{
    int ans=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') 
    {
        if(ch=='-') f*=-1;
        ch=getchar();
    }
    ans=ch-'0';
    ch=getchar();
    while(ch>='0'&&ch<='9') ans*=10,ans+=ch-'0',ch=getchar();
    return ans;
}
const int N=2e5+5;
int n,m,l;
int num[N],rode[N],dis1[N],disn[N],along[N];
struct edge{
    int u,v,nex,w;
}edge[N<<1];
struct node{
    int u,dis;
    node(int uu,int diss){u=uu,dis=diss;}
    bool operator <(const node &x)const{
        return dis>x.dis;//注意符号，我们要小根堆
    }
};
priority_queue<node>s;
int head[N],top=0;
void add(int u,int v,int w)//日常加边
{
    edge[++top].v=v;
    edge[top].u=u;
    edge[top].w=w;
    edge[top].nex=head[u];
    head[u]=top;
}
bool vis[N],viss[N<<1];
void SPFA(int S)//日常SPFA
{
    queue<int>q;
    for(int i=1;i<=n;i++) vis[i]=0;
    q.push(S);
    vis[S]=1; 
    while(!q.empty())
    {
        int u=q.front(); q.pop(); 
        vis[u]=0;
        for(int i=head[u];i;i=edge[i].nex)
        {
            int v=edge[i].v;
            if(!viss[i]&&dis1[v]>dis1[u]+edge[i].w)//不能过原最短路上的边，保证只走远路
            {
                dis1[v]=dis1[u]+edge[i].w;
                if(num[v]) s.push(node(num[v],dis1[v]+disn[num[v]]));//跑回最短路就插入堆
                else if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    n=read(),m=read(),l=read();
    for(int i=1,u,v,w;i<=m;i++) u=read(),v=read(),w=read(),add(u,v,w);
    for(int i=1;i<=l;i++)//标记最短路
    {
        rode[i]=read();
        along[i+1]=edge[rode[i]].v;//记录点
        num[along[i+1]]=i+1;//对最短路上的点编号
        viss[rode[i]]=1;//记录最短路的边
    } 
    for(int i=l;i;i--) disn[i]=disn[i+1]+edge[rode[i]].w;//求出到n点的最短距离
    memset(dis1,0x3f,sizeof(dis1));//到1点的最短路，服务于SPFA
    dis1[1]=0;
    along[1]=1;
    SPFA(1);
    for(int i=1;i<=l;i++)
    {
        while(!s.empty()&&s.top().u<=i) s.pop();//没有绕开断边
        printf("%d\n",s.empty()?-1:s.top().dis);//用堆求解
        dis1[edge[rode[i]].v]=dis1[edge[rode[i]].u]+edge[rode[i]].w;//更新到1点的最短路，服务于SPFA
        SPFA(edge[rode[i]].v);
    }
    return 0;//完结撒花
}

看在这么长的题解+图片上，点个赞再走嘛。