当前位置: 首页 > news >正文

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

 [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$的由交通部指定的最短路径上的道路的编号。

输出格式:

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

输入输出样例

输入样例
4 5 2
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
1 5
输出样例:
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;
}

如果看完后有什么问题 一定要问呀!

转载于:https://www.cnblogs.com/rockyyh/p/10057815.html

相关文章:

  • Centos6.9安装JDK1.8
  • Android Studio中SVN的使用
  • MySQL索引原理以及类型
  • Java语法
  • Linux中的find(-atime、-ctime、-mtime)指令分析
  • vue中watch,computed,mehtod执行顺序
  • Java基础-时间类
  • 如何使用“预训练的词向量”,做文本分类
  • 字符串匹配基础上
  • Curator教程(一)快速入门
  • 阿里云搭建hadoop集群服务器,内网、外网访问问题(详解。。。)
  • 枚举与switch组合使用
  • 如何用纯 CSS 创作一个货车 loader
  • 阿里云马劲:保证云产品持续拥有稳定性的实践和思考
  • C# 获取对象 大小 Marshal.SizeOf (sizeof 只能在不安全的上下文中使用)
  • [译] 怎样写一个基础的编译器
  • CentOS 7 防火墙操作
  • HTML5新特性总结
  • javascript数组去重/查找/插入/删除
  • Java深入 - 深入理解Java集合
  • JS基础篇--通过JS生成由字母与数字组合的随机字符串
  • MySQL常见的两种存储引擎:MyISAM与InnoDB的爱恨情仇
  • Netty 4.1 源代码学习:线程模型
  • SegmentFault 2015 Top Rank
  • SpiderData 2019年2月25日 DApp数据排行榜
  • 动态魔术使用DBMS_SQL
  • 干货 | 以太坊Mist负责人教你建立无服务器应用
  • 官方解决所有 npm 全局安装权限问题
  • 基于组件的设计工作流与界面抽象
  • 模型微调
  • 算法-插入排序
  • 协程
  • 一份游戏开发学习路线
  • 我们雇佣了一只大猴子...
  • ​Spring Boot 分片上传文件
  • #免费 苹果M系芯片Macbook电脑MacOS使用Bash脚本写入(读写)NTFS硬盘教程
  • $.proxy和$.extend
  • (01)ORB-SLAM2源码无死角解析-(66) BA优化(g2o)→闭环线程:Optimizer::GlobalBundleAdjustemnt→全局优化
  • (10)Linux冯诺依曼结构操作系统的再次理解
  • (Pytorch框架)神经网络输出维度调试,做出我们自己的网络来!!(详细教程~)
  • (深度全面解析)ChatGPT的重大更新给创业者带来了哪些红利机会
  • ****** 二 ******、软设笔记【数据结构】-KMP算法、树、二叉树
  • .NET/C# 编译期能确定的字符串会在字符串暂存池中不会被 GC 垃圾回收掉
  • .NET/C# 使用反射注册事件
  • .w文件怎么转成html文件,使用pandoc进行Word与Markdown文件转化
  • @ 代码随想录算法训练营第8周(C语言)|Day57(动态规划)
  • @Autowired多个相同类型bean装配问题
  • [ 数据结构 - C++] AVL树原理及实现
  • [20150321]索引空块的问题.txt
  • [android] 练习PopupWindow实现对话框
  • [BeginCTF]真龙之力
  • [BZOJ1053][HAOI2007]反素数ant
  • [CSS] - 修正IE6不支持position:fixed的bug
  • [CSS]CSS 的背景
  • [LeetCode]-225. 用队列实现栈