标签:图论-最短/最长路

双倍经验:洛谷4568,只需要改数据范围。题意有一个 $n(n\le 10000)$ 点 $m(m\le 50000)$ 边的无向图,可以将其中 $k(k\le 20)$ 条边的边权改成 $0$ ,求 $1\rightarrow n$ 的最短路。题解分层图最短路。将图分为 $k+1$ 层,同一层按给出的边连边;第 $i$ 层与第 $i+1$ 层之间也按给出的边连,但权值为 $0$ 。这样走到...
题解 图论-最短/最长路
省选/NOI-
题意有一个 $m(m\le 20)$ 个点 $e$ 条边的无向图,有 $n(n\le 100)$ 个时刻需要从 $1\rightarrow m$ (保证可以到达)。每个点都有些时刻无法通行,如果更换道路还需要额外交 $k$ 元。求最小花费。题解用 $f[i]$ 表示前 $i$ 个时刻的最小花费,$x$ 表示最短路径。枚举与 $i$ 路径相同的区间起点 $j$ ,可以得到方程:$$f[i]=\...
题解 图论-最短/最长路 动态规划-线性DP
提高+/省选-
题意给出一个 $N$ 点 $M$ 边的有向图,以及 $K$ 个感兴趣的点,求感兴趣的点两两之间最短路的最小值。$N\le 100000 \ , \ M\le 500000$ 。题解如果建立原点和汇点,把 $K$ 个点分成两组,分别与原点汇点相连,再从原点开始跑到汇点的最短路就是最小值。但这样显然无法涵盖所有情况。所以枚举二进制位,把当前位为 $1$ 的加入第一组,其它的放入第二组。因为两个数...
题解 图论-最短/最长路 图论
NOI/NOI+/CTSC
题意给出一个 $N$ 点 $M$ 边的有向图,并给出最短路径。依次删掉最短路上的每条边,求删边后最短路长度。$N\le 10^5 \ , \ M\le 2\times 10^5$ 。题解朴素的做法可以每删一条边就跑一次 $\text{Spfa}$ ,但这样显然会爆。可以发现不需要每次都更新所有点的最短路。如果删除 $(u,v)$ ,那么最短路一定是 $$1\rightarrow x\righ...
题解 图论-最短/最长路 图论
NOI/NOI+/CTSC
题意给出一个 $N$ 点 $M$ 边的有向图,要从 $1\rightarrow D$ 。每条边上有限速,如果限速为 $0$ 则需要按照上一条边的速度走。求最短用时。$N\le 150$ 。题解给朴素的最短路加上一维,用 $dis[x][s]$ 表示在节点 $x$ ,当前速度为 $s$ 的最短用时。然后跑 $\text{Spfa}$ 即可。tips: 对 double 进行 memset 时最...
题解 图论-最短/最长路 图论
提高+/省选-
题意给出一个 $N$ 点无向图,至少有两个连通块。求连接两个连通块的方案,使得新连通块的直径最小。$N\le 150$ 。题解先用 $\text{Floyd}$ 跑最短路,然后可以算出从每个点出发的最远距离,然后枚举两个不连通的点连上即可得到答案。但有可能出现连接的两个点不是直径两端的情况,这时原来连通块的直径就是这个新连通块的直径,所以需要取最大值。#include<bits/std...
题解 图论-最短/最长路 图论
提高+/省选-
题意要从一个 $N$ 点 $M$ 边的有向图的 $1\rightarrow N$ ,每秒可以走 $2^k$ 条边($k$ 是任意自然数),求最少要花多少秒。$N\le 50 \ , \ M\le 10000$ 。题解用一个 bool 数组 $s[i][j][p]$ 表示能否走 $2^p$ 条边从 $i\rightarrow j$ ,可以通过倍增预处理出所有情况。这样就得到了所有能在 $1s$...
题解 图论-最短/最长路 算法-倍增
提高+/省选-
题意有 $N$ 个数和 $M_1+M_2$ 种关系。前 $M_1$ 种关系 $(x,y)$ 表示 $S_x+1=S_y$ ,后 $M_2$ 种关系表示 $S_x\le S_y$ 。求最多有多少个数字值。如果无解输出 NIE 。$N\le 600 , M_1+M_2\le 100000$ 。题解不等式关系可以先差分约束建图。边 $(x,y)$ 的权值表示 $S_x-S_y$ 的最大值,对于 $...
题解 图论-最短/最长路 图论-差分约束 图论-Tarjan
省选/NOI-
题意令 $C_{s,t}$ 表示从 $s$ 到 $t$ 的不同的最短路的数目,$C_{s,t}(v)$ 表示经过 $v$ 从 $s$ 到 $t$ 的最短路的数目;则定义:$$ I(v)=\sum_{s \ne v,t\ne v} \frac{C_{s,t}(v)}{C_{s,t}}$$其中点数 $n\le 100$ ,边数 $m\le 4500$ 。题解$n\le 100$ ,又要统计所有节...
题解 图论-最短/最长路
提高+/省选-
题意给出一张无向连通图,求 $S$ 到 $E$ 经过 $N$ 条边的最短路。其中边数 $T\le 100$ ,点的编号 $\le 1000$ ,$N\le 10^6$ 。题解因为是连通图,所以点最多有 $T+1\le 101$ 个。显然 $O(T^3)$ 的 $\text{Floyd}$ 是可以接受的。考虑 $\text{Floyd}$ 的过程:$$\text{dis[i][j]}=\min...
题解 图论-最短/最长路 思维题 数学-矩阵
提高+/省选-
题意给出一个 $n$ 点 $m$ 边的有向图,从 $1$ 出发再回到 $1$ ,途中要逆行一次,问途中最多经过多少个点。$n,m\le 10^{5}$ 。题解显然要缩点,缩点后点权即为连通分量中点的个数 $\text{siz[]}$ 。然后对强连通分量重新建边,正边为 $\text{edge2}$ ,反边为 $\text{edge3}$ 。对正边跑最长路得到以 $1$ 为起点的最长路 $\t...
题解 图论-最短/最长路 图论-Tarjan
省选/NOI-
题意给出一个有点权的无向图,有的节点有酒吧。从起点出发,需要找到以酒吧为终点的路径,每个节点可以经过任意次,求路径上点权和的最大值。其中点数 $N\le 500000$ ,边数 $M\le 500000$ 。题解缩点,转化为DAG后跑最长路即可。最后取有酒吧的节点中最长路的最大值。#include<bits/stdc++.h> using namespace std; inl...
题解 图论-最短/最长路 图论-缩点
提高+/省选-
题意给一个有向图,如果有负权回路输出-1,否则输出从起点 $S$ 到各个点的最短路长度,如果不连通输出NoPath。其中点数 $N\le 1000$ ,边数 $M\le 100000$ 。题解做法很显然,就是判负环+最短路。最开始我用的深搜 $spfa$ 判负环,求最短路就顺便继续用,然后就很开心的被卡超时了。正解就是用广搜 $spfa$ ,但我又不想删判负环的所以就写了两个。#includ...
题解 图论-最短/最长路 图论-负环
题意给出一个有向图,需要从 $1$ 走到 $N$ ,可以在一个城市买水晶球并在另一个城市卖掉,也可以不买,问最多能赚多少钱。其中 点数$n\le 100000$ ,边数$m\le 500000$ 。题解分层图最短路。对于原图,买卖操作各建一层图,边权为在起点买卖水晶球的花费(买为负卖为正)。给原图、买、卖分别编号为 $1,2,3$ 。已知 $x$ 点买卖水晶球的花费为 $s[x]$ ,对于每...
题解 图论-最短/最长路
提高+/省选-
题意给一个无向图,求严格次小最短路。其中点数 $N\le 5000$ ,边数 $R\le 100000$ 。题解在跑最短路的时候维护一个次短路即可。具体做法是每次枚举的边权先与最短路比较,将较小值给最短路,较大值再与次短路比较。剪枝是如果当前枚举的边比次短路还大就退出。需要注意的是不能用 $vis[]$ 数组来进行判重,可能是因为次短路的缘故不只跑一次吧。#include<bits/s...
题解 图论-最短/最长路
提高+/省选-
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划50 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP14 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP2 图论4 图论-LCA3 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路17 图论-树上差分2 图论-桥1 图论-缩点4 图论-负环3 字符串3 字符串-kmp2 思维题3 数学25 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分10 数据结构-线段树3 数据结构-队列1 比赛-Codeforces19 比赛-JX Round1 比赛-NOIp/CSP4 算法-KM算法1 算法-二分/三分11 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希1 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索20 算法-模拟5 算法-状态压缩4 算法-贪心8 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2