动态删边SPFA： [HNOI2014]道路堵塞

佚名 5年前 (2018-12-03) 算法 1618人围观抢沙发百度已收录

[HNOI2014]道路堵塞

题目描述

$A$ 国有 $N$座城市，依次标为$1$到$N$。同时，在这$N$座城市间有$M$条单向道路，每条道路的长度是一个正整数。现在，$A$国交通部指定了一条从城市$1$到城市$N$的路径，并且保证这条路径的长度是所有从城市$1$到城市$N$的路径中最短的。不幸的是，因为从城市$1$到城市$N$旅行的人越来越多，这条由交通部指定的路径经常发生堵塞。现在$A$国想知道，这条路径中的任意一条道路无法通行时，由城市$1$到$N$的最短路径长度是多少。

输入输出格式

输入格式：

输入文件第一行是三个用空格分开的正整数$N,\ M$和$L$，分别表示城市数目、单向道路数目和交通部指定的最短路径包含多少条道路。按下来$M$行，每行三个用空格分开的整数$a,\ b$和$c$，表示存在一条由城市$a$到城市$b$的长度为$c$的单向道路。这M行的行号也是对应道路的编号，即其中第$1$行对应的道路编号为$1$，第$2$行对应的道路编号为$2$，...，第M行对应的道路编号为$M$。最后一行为$L$个用空格分开的整数$sp_1$ ...，，$sp_L$，依次表示从城市$1$到城市$N$的由交通部指定的最短路径上的道路的编号。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。输出格式：

输出文件包含$L$行，每行为一个整数，第$i$行$(i=1,\ 2, ...,L)$的整数表示删去编号为$sp_i$的道路后从城市1到城市N的最短路径长度。如果去掉后没有从城市$1$到城市$N$的路径，则输出$-1$。

输入输出样例

输入样例

输出样例：

6
6

主要是网上关于这题的题解分析太少了希望能写一篇可以让大家看懂的……

这题是一道动态删边SPFA + 堆的题说白了，就是SPFA乱搞

理论基础

首先，本题很友好的把一开始的最短路告诉了我们，且删掉的边都在最短路上，(正常动态删边，如果不是删的最短路上的边，直接输出最短路即可，所以本题就是动态删边最难搞的一部分，删了最短路上的边)

当你删掉一条边$（u -> u+1）$时，最短路必为 $1 -> x(x <= u) -> y（y >= u+1） -> n $其中有且仅有 $1 -> x$ 与 $y -> n $为原最短路上的路线

比如：

该图的最短路很明显为$1->3->4->5$

如果我们任意去掉一条最短路上的边$（1->3或3->4或4->5)$，很不巧，答案都是$1->2->5(Lenmin = 7)$，均满足$1 -> x(x <= u) -> y（y >= u+1） -> n$（好吧本图有点特殊）

搞定这个后，我们可以先把所有最短路上的点记录一下，并将其到1及到n的距离预处理出来

    st[1] = pos[1] = 1;
    for(register int i = 1;i<=L;i++)
    {
        scanf("%d",&path[i]);
        pos[ed[path[i]]] = i+1;//该点在最短路上是第几个
        st[i+1] = ed[path[i]];//最短路上第i+1个点是哪个点
    }
    for(register int i = 2;i<=L;i++)f[i] = f[i-1] + vlu[path[i-1]];//Why not + -> L+1（n点）：只删L条边 不可能从n点为起点 
    for(register int i = L;i>=2;i--) g[i] = g[i+1] + vlu[path[i]]; // Why not 是 i -> 2 同 ↑

接着枚举每一条最短路上的边，删了它并分别做一次SPFA

重点来了，怎么SPFA！

首先是普通的$vis$和$dis$及$queue$

设起点为$u$

当搜到一个普通点时，和原SPFA一样，但如果搜到一个在最短路上的点且这个点在最短路上排在$u$的后面，就满足了上面的条件，有可能是最优解，我们可以把它放入一个栈$s$里，且打个标记该点在栈里；如果已经在栈里，只要更新它的$x$（$tmp$数组中的$x$即为$value$,$id$为该点的编号）

最后搜完后将所有可能为答案的点及它所带来的答案加入到一个小根堆，然后弹出编号在$u$之前的点，则小根堆的top的答案即为最短路答案

可能会有的一些问题（有一些写为代码注释）

1.Why dis不用memset

如上图，第一条边做好后，$dis_2$是3，如果memset后，从3开始搜，$dis_2$就会变为5，就再也找不到1-2-5了；所以$dis_x$在本题的实质是以$1-x$（正在搜的点）为起点的最短的距离

2.在SPFA中，加入栈的都被特判过是在u之后，为什么还要弹出点

咳咳，同学，我们在搜下一条边之前并没有清空操作，有可能有是之前的答案但不符合现在的答案

3.……本人暂时没想到，不过有问题随便问

对了，上代码！

#include<bits/stdc++.h>
#define MAXN 110000
#define MAXM 210000
#define INF 2147483647
using namespace std;
int pos[MAXN],st[MAXN]; // pos[i] i点为原最短路上的第几个点 st[i]  最短路上的第i个点是谁 
int hed[MAXN],nxt[MAXM],ed[MAXM],vlu[MAXM],l = 0; // 普通邻接表
int dis[MAXN];
int path[MAXN]; // 原最短路 
bool used[MAXN];//该点是否在栈里
int f[MAXN],g[MAXN]; // f[i]表示 1 - st[i] g[i] 表示 ed[i] - n 
int n,m,L;
struct Point 
{
    int x,id;
}tmp[MAXN];
inline bool operator < (const Point & A,const Point & B) {return A.x > B.x;}//变为小根堆
priority_queue < Point > Q;
inline void Line(int u,int v,int w) // 邻接表加边 
{
    nxt[++l] = hed[u];
    hed[u] = l;
    ed[l] = v;
    vlu[l] = w;
}
inline int read() 
{
    int s = 0;char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') {s = s * 10 + ch - '0';ch = getchar();}
    return s;
}
inline void SPFA(int u)
{
    bool vis[MAXN];
    memset(vis,0,sizeof(vis));
    memset(used,0,sizeof(used));
    stack <int> s;
    queue <int> q;
    q.push(st[u]);
    vis[st[u]] = 1;
    dis[st[u]] = f[u];
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        vis[k] = 0;
        for(register int i = hed[k];i;i = nxt[i])
        {
            if(i == path[u]) continue;
            if(pos[ed[i]] > u)//可能是答案
            {
                if(!used[ed[i]])//将该点加入栈里
                {
                    used[ed[i]] = 1;
                    s.push(ed[i]);
                    tmp[ed[i]].id = pos[ed[i]];
                    tmp[ed[i]].x = dis[k] + vlu[i] + g[pos[ed[i]]];
                }
                else tmp[ed[i]].x = min(tmp[ed[i]].x,dis[k] + vlu[i] + g[pos[ed[i]]]);//将该点的value更新
            }
            else if(dis[ed[i]] > dis[k] + vlu[i])//普通点
            {
                dis[ed[i]] = dis[k] + vlu[i];
                if(!vis[ed[i]]) q.push(ed[i]),vis[ed[i]] = 1;
            }
        }
    }
    while(!s.empty()) Q.push(tmp[s.top()]),s.pop();//将点出栈
}
int main()
{
    n = read(),m = read(),L = read();
    for(register int i = 1;i<=m;i++)
    {
        int a = read(),b = read(),c = read();
        Line(a,b,c);
    }
    st[1] = pos[1] = 1;
    for(register int i = 1;i<=L;i++)
    {
        scanf("%d",&path[i]);
        pos[ed[path[i]]] = i+1;
        st[i+1] = ed[path[i]];
    }
    for(register int i = 2;i<=L;i++) f[i] = f[i-1] + vlu[path[i-1]];//Why not + -> L+1（n点）：只删L条边 不可能从n点为起点 
    for(register int i = L;i>=2;i--) g[i] = g[i+1] + vlu[path[i]]; // Why not i -> 2 同 ↑
    for(register int i = 1;i<=n;i++) dis[i] = INF;
    for(register int i = 1;i<=L;i++)
    {
        SPFA(i);
        while(!Q.empty() && Q.top().id <= i) used[Q.top().id] = 0,Q.pop();//将无用的点去掉
        if(Q.empty()) printf("-1\n");
        else printf("%d\n",Q.top().x);
    }
    return 0;
}