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

题意有 $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...
题解 图论-最短/最长路
提高+/省选-
题意求 从$1$ 到 $N$ 的一条路径,使得第 $K+1$ 长的边权尽可能小。其中点数 $N\le 1000$ ,边数 $P\le 2000$,权值 $L_i\le 10^{6}$题解直接求肯定没有办法,所以考虑二分答案。对第 $K+1$ 长的边权 $x$ 进行二分,每次检验就跑一次 $Dijkstra$ ,只是把边权变为 $>x$ 的边的条数,这样就可以得到$>x$ 的边最少...
题解 图论-最短/最长路
提高+/省选-
卧槽竟然一遍就A了,可把身为蒟蒻的我nb坏了刚开始让我做这道题,我是拒绝的,然后看完题发现,这就是道裸的最短路,连边搞就是了。然后发现它只给三个点,看了题解才知道第四个点可以用向量点乘判断垂直来求,路燕我对不起你。思路就是把一个城市分成四个点,同一个城市坐车,不同城市坐飞机,得到所有点的坐标和所在城市以后跑一遍最短路就行了。因为我很菜只会dijkstra,所以我就写的dijkstra。#de...
题解 图论-最短/最长路
提高+/省选-