夢に僕らで帆を張って
来るべき日のために夜を超え

标签 最短路 下的文章

November 11, 2019

CF543B Destroying Roads

题意在这个国家有$n$个城市,城市间由$m$条双向公路连接。城市被编号为$1$到$n$ 。如果城市$a$和$b$被公路连接,那么你可以双向通行。你可以在这个公路网上通过公路从一个城市移动到另一个城市。走过每条公路均耗时$1$小时你想要破坏最多的公路,但是破坏后必须满足从指定城市$s_1$ 到$t_1$最短不超过$l_1$小时,且从指定城市$s_2$到$t_2$最短不超过$l_2$​ 小时计算...
November 11, 2019

CF449B Jzzhu and Cities

题意$n$个点,$m$条带权边的无向图,另外还有$k$条特殊边,每条边连接$1$和$i$问最多可以删除这$k$条边中的多少条,使得每个点到$1$的最短距离不变数据范围:$1 \le n,k \le 10^5,1\le m \le 3\times 10^5$题解最短路计数,判断这几条边是否再最短路上或这几个点有没有别的最短路可以达到代码:#include<iostream> #in...
November 9, 2019

洛谷P4009 汽车加油行驶问题

题意略数据范围:$2 \le n \le 100,2 \le k \le 10$题解将油量视为状态,分层建图之后跑最短路即可(也可跑费用流)代码:#include<iostream> #include<cstdio> #include<queue> #include<memory.h> using namespace std; const in...
October 31, 2019

洛谷P3831/SHOI2012 回家的路

题意$n \times n$的网格图中有$m$个点可转向,求最短路数据范围:$n \le 20000,m \le 100000$题解分层图两层图,每层只建一种方向的边(纵/横),连接两层之间表示转向代码:#include<iostream> #include<cstdio> #include<algorithm> #include<cstring&g...
October 31, 2019

洛谷P1948/USACO08JAN 电话线Telephone Lines

题意无向图中,可选择$k$条边将边权变为$0$,求最小瓶颈最短路数据范围:$1 \le n,k \le 1000,1 \le m \le 10000$题解分层图每层内建原图,在层之间建边权为$0$的单向边,意为一次变化,因此共$k+1$层为统计答案,由每一层的终点向超级汇点连一条权值为$0$的单向边代码:#include<iostream> #include<cstdio&...
October 31, 2019

CF786B Legacy

题意有$3$种连边方式$u \rightarrow v$ 点向点$u \rightarrow [l,r]$ 点向区间$[l,r] \rightarrow u$ 区间向点求从$s$出发的最短路数据范围:$1 \le n,q \le 10^5$题解显然对于向区间建边不能一个一个建,那么能不能直接向整个区间建边呢?联想到线段树的一个节点维护一个区间的信息,那么可以向这个节点建边;这便是线段树优化建...
October 31, 2019

洛谷P2384 最短路

题意求乘积最短路数据范围:$n \le 1000,m \le 1000000$题解由于需要松弛,不能对乘积取模,而这又会导致爆$\text{long long}$因此需要一个单增的函数来反映距离大小容易想到$\log$代码:#include<iostream> #include<cstdio> #include<cmath> #include<alg...
October 30, 2019

洛谷P4768/NOI2018 归程

题意略数据范围:$n \le 200000,m \le 400000,q \le 400000$ [强制在线]题解分析题意:需要找到一个节点$u$,使得从起点$v \rightarrow u$上的所有节点的海拔$> p$,并且使得从$u \rightarrow 1$距离最小第一个要求可以用$\mathrm{Kruskal}$重构树解决(以海拔为关键字降序建立);因为重构树是小根堆,所以...