dw做游戏网站代码,郑州众志seo,旅业认证二维码有什么用,做分子生物实验常用网站目录 图论学习总结前言一、基础知识图的存储图的遍历 二、最短路多源最短路 F l o y d Floyd Floyd 算法例题及变形 e g 1 #xff1a; S o r t i n g I t A l l O u t eg1#xff1a;Sorting\ It\ All\ Out eg1#xff1a;Sorting It All Out ( 蓝书例题#xff0c;传递… 目录 图论学习总结前言一、基础知识图的存储图的遍历 二、最短路多源最短路 F l o y d Floyd Floyd 算法例题及变形 e g 1 S o r t i n g I t A l l O u t eg1Sorting\ It\ All\ Out eg1Sorting It All Out ( 蓝书例题传递闭包 ) (蓝书例题传递闭包) (蓝书例题传递闭包) e g 2 : S i g h t s e e i n g t r i p eg2:Sightseeing\ trip eg2:Sightseeing trip ( 蓝书例题 F l o y d 求最小环 ) (蓝书例题Floyd求最小环) (蓝书例题Floyd求最小环) e g 3 : C o w R e l a y s eg3:Cow\ Relays eg3:Cow Relays ( 蓝书例题倍增优化 D P o r 广义矩阵乘法 快速幂优化 ) (蓝书例题倍增优化DP\ or\ 广义矩阵乘法快速幂优化) (蓝书例题倍增优化DP or 广义矩阵乘法快速幂优化) 练习题 单源最短路知识点例题及变形 e g 1 : 最优贸易 eg1: 最优贸易 eg1:最优贸易 ([B-最优贸易_ ](https://ac.nowcoder.com/acm/contest/1055/B)) e g 2 : R o a d a n d P l a n e s eg2:Road\ and\ Planes eg2:Road and Planes ([C-Roads and Planes_0x61 图论-最短路](https://ac.nowcoder.com/acm/contest/1055/C)) e g 3 : T h e r e a n d B a c k A g a i n eg3:There\ and\ Back\ Again eg3:There and Back Again [ 2024 I C P C 2024ICPC 2024ICPC亚太锦标赛 J ](https://codeforces.com/problemset/problem/1938/J) e g 4 : P e r m u t a t i o n P u z z l e eg 4:Permutation\ Puzzle eg4:Permutation Puzzle [ 2023 C C P C G u i l i n − J 2023\ CCPC\ Guilin - J 2023 CCPC Guilin−J ](https://codeforces.com/gym/104008/problem/J)(金牌题拓扑排序DP贪心) e g 5 : eg5: eg5: [ N O I P 2017 ] [NOIP2017] [NOIP2017]P3953 [NOIP2017 提高组\] 逛公园 - 洛谷 | 计算机科学教育新生态 ](https://www.luogu.com.cn/problem/P3953) 欧拉回路差分约束系统 e g 1 : eg1: eg1: [P3275 SCOI2011 糖果 - 洛谷](https://www.luogu.com.cn/problem/P3275)差分约束 0 / 1 0/1 0/1 分数规划[A-Sightseeing Cows(nowcoder.com)](https://ac.nowcoder.com/acm/contest/1059/A)spfa判负环二分求解01分数规划问题 练习题 三、树论以及图的联通性最小生成树 e g 1 : eg1: eg1: [A-走廊泼水节(nowcoder.com)](https://ac.nowcoder.com/acm/contest/1056/A)克鲁斯卡尔思想的灵活运用 e g 2 eg2 eg2[B-Picnic Planning (nowcoder.com)](https://ac.nowcoder.com/acm/contest/1056/B)码量较大 生成树计数 L C A LCA LCA、树上差分及应用知识点例题 e g 1 : eg1: eg1: [巡逻 ](https://ac.nowcoder.com/acm/contest/1057/A)树的直径 e g 2 : eg2: eg2: [闇の連鎖_](https://ac.nowcoder.com/acm/contest/1057/C)(树上差分) e g 3 : eg3: eg3: [E-天天爱跑步](https://ac.nowcoder.com/acm/contest/1057/E) e g 4 : eg4: eg4: [F-异象石_](https://ac.nowcoder.com/acm/contest/1057/F) e g 5 : eg5: eg5: [G-次小生成树_](https://ac.nowcoder.com/acm/contest/1057/G) e g 6 : eg6: eg6: [H-疫情控制_](https://ac.nowcoder.com/acm/contest/1057/H) 基环树 e g 1 : eg1: eg1: [岛屿_](https://ac.nowcoder.com/acm/contest/1058/A) e g 2 : eg2: eg2: [B-创世纪_](https://ac.nowcoder.com/acm/contest/1058/B) e g 3 : eg3: eg3:[K-牛镇公务员考试](https://ac.nowcoder.com/acm/contest/67741/K)基环树一般的处理方式 e g 4 : S u g a r S w e e t I I eg4:Sugar\ Sweet II eg4:Sugar SweetII [2023_ICPC_杭州站 - H - Codeforces](https://codeforces.com/gym/492111/problem/H)基环树 概率1/2个银牌题 练习题 四、二分图及图匹配二分图常见模型二分图例题 e g 1 : eg1: eg1: [ Z J O I 2009 ZJOI2009 ZJOI2009\][假期的宿舍](https://ac.nowcoder.com/acm/contest/34649/B)(二分图最大匹配板题) e g 2 : eg2: eg2: [C-Going Home](https://ac.nowcoder.com/acm/contest/34649/C)二分图带权匹配KM算法 e g 3 : eg3: eg3: [棋盘覆盖](https://ac.nowcoder.com/acm/contest/34649/F)蓝书例题 e g 4 : eg4: eg4: [L-城市物流](https://ac.nowcoder.com/acm/contest/34649/L)cf上也有对应原题rating 2600二分图匹配模型综合题 一般图匹配练习题 五、网络流初步最大流Maximum flow简称 M F MF MF e g 1 : eg1: eg1: [ P 2764 P2764 P2764 最小路径覆盖问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P2764) 最小费用最大流Minimum cost maximum flow简称 M C M F MCMF MCMF常见的建模思路 六、综合模型及应用(以题目总结为主)分层图思想 e g 1 : 通信线路 eg1:通信线路 eg1:通信线路[A-Telephone Lines](https://ac.nowcoder.com/acm/contest/1055/A)(蓝书例题) e g 2 : 小雨坐地铁 eg2:小雨坐地铁 eg2:小雨坐地铁 [1012-小雨坐地铁(nowcoder.com)](https://ac.nowcoder.com/acm/contest/26077/1012) e g 3 : G . B i c y c l e s eg3: G. Bicycles eg3:G.Bicycles [Problem - 1915G - Codeforces](https://codeforces.com/problemset/problem/1915/G)(注意带点贪心剪枝) e g 4 : R i n n e L o v e s G r a p h eg4: Rinne\ Loves\ Graph eg4:Rinne Loves Graph [NC22594, 1031-Rinne Loves Graph(nowcoder.com)](https://ac.nowcoder.com/acm/contest/26077/1031) 平面图思想最短路图其他拆点建图搭平台建图 e g 1 : eg1: eg1:[Meeting (nowcoder.com)](https://ac.nowcoder.com/acm/contest/26077/1022)(UVALive7250 / hduoj 552115年沈阳站银牌题) e g 2 : eg2: eg2: [Problem - 1941G - Codeforces](https://codeforces.com/problemset/problem/1941/G)(搭平台跑最短路相当于把图集合化cf rating 2000) 最小树形图 e g 1 : eg1: eg1: [1036-\[ S C O I 2012 SCOI2012 SCOI2012] 滑雪与时间胶囊](https://ac.nowcoder.com/acm/contest/26077/1036) 模型综合运用练习题 参考资料最小树形图 e g 1 : eg1: eg1: [1036-\[ S C O I 2012 SCOI2012 SCOI2012] 滑雪与时间胶囊](https://ac.nowcoder.com/acm/contest/26077/1036) 模型综合运用练习题 参考资料 图论学习总结
前言
**这是个人的图论学习刷题总结圈内的开源氛围挺好的发出来希望对大家的训练有所帮助个人水平有限如果有误希望帮忙指出。**这篇博客涉及算法思想和例题以及相关解法和思路所有例题和练习题本人均已ac部分题提供ac代码地址(python)部分题不开另外时限python ac不了的会考虑提供 C实现。本人学习图论是以蓝书《算法竞赛进阶指南》为教材然后听了听牛客进阶课的图论专题这篇博客所涉及到的题目基本包含蓝书图论的所有例题还包括牛客上的一些题目以及个人 X C P C 训练或比赛时 XCPC训练或比赛时 XCPC训练或比赛时遇到的一些图论题注例题没有刻意的按难度排序附上的题目连接以 Codeforces, NowCoder, 洛谷为主。这篇博客在退役前会持续更新目前例题还有很多题解没完善的还有没加上例题的慢慢更新吧TAT大概每个月重新上传一次吧其中知识点大多以无序表的形式给出大纲较多对于基本算法知识点不会的朋友可以自己利用搜索引擎学习这些知识。
一、基础知识
图的存储
邻接矩阵 二维数组 A [ i , j ] w ( i , j ) A[i,j] w(i,j) A[i,j]w(i,j) , O ( n 2 ) O(n^2) O(n2)注意重边 邻接表(数组模拟链式前向星) 表头数组 h e a d [ N ] ( 指向从某点出发的第 1 条边 ) head[N](指向从某点出发的第1条边) head[N](指向从某点出发的第1条边)边集大小 t o t tot tot边集数组 $ verMedgeMnextM$ 邻接表( C C C v e c t o r vector vector P y t h o n Python Python l i s t list list)
图的遍历
深度优先遍历 访问标记避免重复、时间戳( d f s dfs dfs序: d f n dfn dfn) 广度优先遍历 循环队列、优先队列边权为01的图上双端队列 拓扑排序 判定有向无环图(DAG)
二、最短路
多源最短路 F l o y d Floyd Floyd 算法
令 D [ i , j ] D[i,j] D[i,j] 表示**“经过若干个编号不超过k的结点”** 从 i i i 到 j j j 的最短路。该问题可以划分为两个子问题经过编号不超过 k − 1 k-1 k−1 的结点从 i i i 到 j j j或者先从 i i i 到 k k k再从 k k k 到 j j j。于是 D [ k , i , j ] m i n ( D [ k − 1 , i , j ] , D [ k − 1 , i , k ] D [ k − 1 , k , j ] ) D[k,i,j] min(D[k-1,i,j], D[k-1,i,k]D[k-1,k,j]) D[k,i,j]min(D[k−1,i,j],D[k−1,i,k]D[k−1,k,j]) 初值为 D [ 0 , i , j ] G [ i , j ] D[0,i,j] G[i,j] D[0,i,j]G[i,j]可以看到 F l o y d Floyd Floyd 的本质是动态规划 k k k 是阶段。其中 k k k 这一维可以省略即 D [ i , j ] m i n ( D [ i , j ] , D [ i , k ] , D [ k , j ] ) D[i,j] min(D[i,j],D[i,k],D[k,j]) D[i,j]min(D[i,j],D[i,k],D[k,j])。
例题及变形 e g 1 S o r t i n g I t A l l O u t eg1Sorting\ It\ All\ Out eg1Sorting It All Out ( 蓝书例题传递闭包 ) (蓝书例题传递闭包) (蓝书例题传递闭包)
题目大意 这是一道传递闭包问题是Floyd算法的简单应用。我们可以对每个形如 i j i j ij 的不等式令 d [ i , j ] 1 d[i,j] 1 d[i,j]1除了 i j ij ij 的其他情况都令 d [ i , j ] 0 d[i,j]0 d[i,j]0。我们可以用Floyd算法对 d d d 求传递闭包若存在 d [ i , j ] d [ j , i ] 1 d[i,j] d[j,i] 1 d[i,j]d[j,i]1 则说明有矛盾若均为0则说明不能确定关系。此时我们可以再用二分法二分 t t t 的值判断仅用前 t t t 个不等式能否判断所有关系。 e g 2 : S i g h t s e e i n g t r i p eg2:Sightseeing\ trip eg2:Sightseeing trip ( 蓝书例题 F l o y d 求最小环 ) (蓝书例题Floyd求最小环) (蓝书例题Floyd求最小环)
题目大意 我们考虑 F l o y d Floyd Floyd 的算法过程。当外层循环 k k k 刚开始时 d [ i , j ] d[i,j] d[i,j] 保存着经过编号不超过 k − 1 k-1 k−1 的结点从 i i i 到 j j j 的最短路长度。于是 min 1 ≤ i j k { d [ i , j ] g [ j , k ] g [ k , i ] } \min_{1\leq ijk}{\{d[i,j]g[j,k]g[k,i]\}} 1≤ijkmin{d[i,j]g[j,k]g[k,i]} 就是满足以下两个条件的最小环长度1、由编号不超过 k k k 的结点构成。2、经过结点 k k k。前面式子中的 i , j i,j i,j 相当于枚举了环上与 k k k 相邻的两个点对 A ∈ [ 1 , n ] A∈[1,n] A∈[1,n] 都进行计算取最小值即是答案(我们在考虑每个 k k k 只考虑了由编号不超过 k k k 的结点构成的最小环由对称性可知这样不会影响答案)。 e g 3 : C o w R e l a y s eg3:Cow\ Relays eg3:Cow Relays ( 蓝书例题倍增优化 D P o r 广义矩阵乘法 快速幂优化 ) (蓝书例题倍增优化DP\ or\ 广义矩阵乘法快速幂优化) (蓝书例题倍增优化DP or 广义矩阵乘法快速幂优化)
题目大意 F l o y d Floyd Floyd 算法是一种以”途径点集大小”为阶段的动态规划算法在这道题我们可以考虑用以边的数量为阶段的 D P DP DP方法经过倍增优化求解。首先对于点的编号我们需要先进行离散化假设离散化后点的数量为 P P P G G G 为 P ∗ P P*P P∗P 的邻接表。我们考虑从 s s s 出发分别经过 2 0 , 2 1 , . . . , 2 N 2^0,2^1,...,2^N 20,21,...,2N 条边到 e e e 的最短路倍增优化的前提是状态可以按阶段任意划分所以我们不妨令 F [ i , x , y ] F[i,x,y] F[i,x,y] 表示从 x x x 出发恰好经过 2 i 2^i 2i 条边到达 y y y。那么状态转移时的决策我们只需要枚举中转点 k k k状态转移方程 F [ i , x , y ] min 1 ≤ k ≤ t o t { F [ i , x , y ] , F [ i − 1 , x , k ] F [ i − 1 , k , y ] } F[i,x,y] \min_{1\le k\le tot} \{F[i,x,y], F[i-1,x,k]F[i-1,k,y] \} F[i,x,y]min1≤k≤tot{F[i,x,y],F[i−1,x,k]F[i−1,k,y]}。
我们进一步考虑其实这道题是一种广义的矩阵乘法可以通过矩阵快速幂优化。我们考虑以下式子 ∀ i , j ∈ [ 1 , P ] B [ i , j ] min 1 ≤ k ≤ P { G [ i , k ] G [ k , j ] } \forall i,j\in[1,P]\ \ B[i,j]\min_{1\le k\le P}\{G[i,k]G[k,j] \} ∀i,j∈[1,P] B[i,j]min1≤k≤P{G[i,k]G[k,j]}在式子中我们枚举了所有的中专点 k k k对于每一对 ( i , j ) (i,j) (i,j) 来说 B B B 记录的是恰好经过两条边的最短路。
若 G m G^m Gm 记录了所有点两两之间恰好经过 m m m 条边的最短路我们可以初始化 a n s G 0 ansG^0 ansG0 a n s [ i ] [ j ] ans[i][j] ans[i][j] 表示恰好经过了 0 0 0 条边从 i i i到 j j j 的最短路。那么 ∀ i , j ∈ [ 1 , P ] , D r m min 1 ≤ k ≤ P { ( D r ) [ i , k ] ( D m ) [ k , j ] } \forall i,j \in[1,P],\ D^{rm} \min_{1\le k\le P}\{(D^r)[i,k](D^m)[k,j] \} ∀i,j∈[1,P], Drmmin1≤k≤P{(Dr)[i,k](Dm)[k,j]}这个式子其实等价于一个关于 min \min min和 的广义的矩阵乘法我们可以先用快速幂计算出 a n s N ans^N ansN最后 ( a n s N ) [ S , E ] (ans^N)[S,E] (ansN)[S,E] 就是答案每次矩阵乘法是 O ( T 3 ) O(T^3) O(T3)一共 log N \log N logN 次时间复杂度为 O ( T 3 log N ) O(T^3\log N) O(T3logN)。
ac代码参考代码查看 (nowcoder.com)
练习题
Gym-104023-Problem - F (2022 C C P C CCPC CCPC威海F金牌题Floyd 建图用类似 P r i m Prim Prim 的做法找出以每个点 s 为根的有向瓶颈生成树)
单源最短路
知识点 D i j k s t r a Dijkstra Dijkstra S P F A SPFA SPFA 和 B e l l m a n − F o r d Bellman-Ford Bellman−Ford S P F A SPFA SPFA 已死 01 B F S 01BFS 01BFS只适用于边权只有0和1的图 拓扑排序 D P 拓扑排序DP 拓扑排序DP (有向无环图)
例题及变形 e g 1 : 最优贸易 eg1: 最优贸易 eg1:最优贸易 (B-最优贸易_ )
题目大意 本题是让我们在一张结点带有权值的图上找出一条从 1 1 1 到 n n n 的路径使得路径上能够找出两个点 p , q p,q p,q v a l p − v a l q val_p-val_q valp−valq 最大。
我们可以把这张图当作有向图处理从结点 1 1 1 出发跑一次 “最短路” 算法预处理出当前结点 x x x 的前驱结点中所有点权的最小权值记为 p r e [ x ] pre[x] pre[x]同理我们可以反向建图从 n n n 出发预处理出在正图中当前结点 x x x 之后所有点权的最大值记为 p a s t [ x ] past[x] past[x]最后枚举每个结点 x x x用 p a s t [ x ] − p r e [ x ] past[x]-pre[x] past[x]−pre[x] 更新答案即可。
注意上述预处理中的 “最短路” 算法可以将松弛操作分别改为 min 和 max \min和\max min和max 那么松弛更新的操作就不满足 D i j k s t r a Dijkstra Dijkstra 的贪心性质我们可以用 S P F A SPFA SPFA 算法。 e g 2 : R o a d a n d P l a n e s eg2:Road\ and\ Planes eg2:Road and Planes (C-Roads and Planes_0x61 图论-最短路)
题目大意 这道题是一个十分明显的单源点最短路问题但图中带有负权边我们不能直接使用 D i j k s t r a Dijkstra Dijkstra又因为有特殊构造的数据所以我们使用 S P F A SPFA SPFA 会 T L E TLE TLE。这时候我们就要注意到**双向边都是非负的只有单向边可能是负的并且单向边不构成环。**我们可以利用这一性质解决本题。
如果我们只看双向边会发现是一个个的连通块连通块内所有边均为非负边权。那么我们可以对每一个连通块内跑 D i j k s t r a Dijkstra Dijkstra 算法。这时候如果我们把每一个连通块看作一个点的话那么加上单向边(航线)那么整个图就是一张有向无环图不管边权正负我们都可以通过 拓扑排序 松弛操作 拓扑排序松弛操作 拓扑排序松弛操作在线性时间内求出最短路。
至此这道题的解法已经很明显了 拓扑排序套 D i j k s t r a 拓扑排序套Dijkstra 拓扑排序套Dijkstra。我们在外层维护每一个连通块的度数 d e g deg deg在每个块内跑 D i j k s t r a Dijkstra Dijkstra遇到负权单向边则更新连通块的度数用于外层的拓扑排序。
整个的时间复杂度为 O ( T P R log T ) O(TPR\log T) O(TPRlogT) 具体实现代码查看 (nowcoder.com) e g 3 : T h e r e a n d B a c k A g a i n eg3:There\ and\ Back\ Again eg3:There and Back Again 2024 I C P C 2024ICPC 2024ICPC亚太锦标赛 J
题目大意 这是一道最短路的变形题目要求从 1 1 1 到 n n n 再到 1 1 1 的最短距离并且要求 1 1 1 到 n n n 和 n n n 到 1 1 1 的路径不相同。
首先我们考虑最短路要想总和最小那么去和回至少有一条是最短路不妨就去时走最短路那么 1 1 1 到 n n n我们可以直接在图中跑 D i j k s t r a Dijkstra Dijkstra 算法记为 d 1 d1 d1考虑回的时候我们可以再以 n n n 为起始点跑一边最短路记为 d 2 d2 d2我们可以枚举每一条边如果不在去的路径中我们用 d 1 [ x ] d 2 [ y ] w d1[x]d2[y] w d1[x]d2[y]w 更新答案其最小值就是我们需要的答案。
实现细节C可以用链式前向星存图边的话就有对应下标开个数组标记即可python的话用邻接表存图直接用set当vis即可ac代码参考( P y t h o n Python Python)Submission #256743872 - Codeforces e g 4 : P e r m u t a t i o n P u z z l e eg 4:Permutation\ Puzzle eg4:Permutation Puzzle 2023 C C P C G u i l i n − J 2023\ CCPC\ Guilin - J 2023 CCPC Guilin−J (金牌题拓扑排序DP贪心)
题目大意
Little r e l y t 871 relyt871 relyt871 is solving a puzzle. The key to the puzzle is a permutation containing numbers 1 … n 1 \dots n 1…n. The values at some positions of the permutation are already fixed, and r e l y t 871 relyt871 relyt871 needs to fill numbers into the remaining positions.
Besides, little r e l y t 871 relyt871 relyt871 has gathered m m m extra requirements about the permutation. Let the solution be represented as p 1 , p 2 , . . . , p n p_1,p_2,...,p_n p1,p2,...,pn, each clue is a pair of indices ( u i , v i ) (u_i,v_i) (ui,vi), which means that p u i p v i p_{u_i} p_{v_i} puipvi should be satisfied in the solution.
Little r e l y t 871 relyt871 relyt871 wonders if all requirements may be satisfied at the same time. Write a program to find a valid solution when there is one.
这是一道灵活运用 拓扑排序 D P 拓扑排序DP 拓扑排序DP求最短路的题想到图论不难难点是想到用图论算法这么做。
根据所给限制建图将 p u p v p_u p_v pupv 的限制视为一条 u → v u → v u→v 的单向边题目保证会得到一个 D A G DAG DAG。 设在 D A G DAG DAG 上存在一条从 u u u 到 v v v 的边数为 k k k 的路径若 p u p_u pu 已知而 p v p_v pv 未知则可以推出 p v ≥ p u k p_v ≥ p_u k pv≥puk 若 p u p_u pu 未知而 p v p_v pv 已知则可以推出 p u ≤ p v − k p_u ≤ p_v − k pu≤pv−k。 首先我们通过上述规则推导出所有位置的取值范围 [ L i , R i ] [L_i , R_i] [Li,Ri]。对于已知位置显然 L i R i p i L_i R_i p_i LiRipi对于未知位置可以用 拓扑排序 d p 拓扑排序 dp 拓扑排序dp 来求解。先正向拓扑排序求出 L L L对于边 ( u , v ) (u, v) (u,v)做转移 L v max ( L v , L u 1 ) L_v \max(L_v, L_u 1) Lvmax(Lv,Lu1)然后反向拓扑排序求出 R R R对于边 ( u , v ) (u, v) (u,v)做转移 R u min ( R u , R v − 1 ) R_u \min(R_u, R_v − 1) Rumin(Ru,Rv−1)。
于是转化为如下问题给定 k k k 个区间和 k k k 个互不相同的数我们需要给每个数匹配一个包含它的区间此外每个区间匹配的数还要满足一些拓扑关系(形如 p u p v p_up_v pupv的约束)。如果暂时不考虑拓扑关系的话是一个经典问题存在一个简单的贪心做法从小到大枚举所有数当枚举到 x x x 时从所有左端点 ≤ x ≤ x ≤x 且还没被匹配的区间中选择右端点最小的那个匹配给 x x x这个过程用优先队列优化。
然后分析一下区间的性质如果存在边 ( u , v ) (u, v) (u,v)根据转移方程可得 L u 1 ≤ L v R u 1 ≤ R v L_u 1 ≤ L_vR_u 1 ≤ R_v Lu1≤LvRu1≤Rv按 照上述贪心做法 [ L u , R u ] [L_u, R_u] [Lu,Ru] 一定比 [ L v , R v ] [L_v, R_v] [Lv,Rv] 更早被匹配到即一定满足 p u p v p_u p_v pupv。所以直接贪心求出来的就是原问题的合法解如果贪心无解则原问题一定无解。 总时间复杂度 O ( m n log n ) O(m n \log n) O(mnlogn)。
启发对于 拓扑排序 D P 拓扑排序DP 拓扑排序DP不仅可以用来就 D A G DAG DAG的最短路对于这种可行解的问题我们可以用 拓扑排序 D P 拓扑排序DP 拓扑排序DP将答案优化到一个区间内此时可能会将问题转化为另一个较简单直白的问题如本题转化为了一个简单的贪心问题。
ac代码参考Submission #256911647 - Codeforces e g 5 : eg5: eg5: [ N O I P 2017 ] [NOIP2017] [NOIP2017]P3953 NOIP2017 提高组] 逛公园 - 洛谷 | 计算机科学教育新生态
题目大意
策策同学特别喜欢逛公园。公园可以看成一张 N N N 个点 M M M 条边构成的有向图且没有自环和重边。其中 1 1 1 号点是公园的入口 N N N 号点是公园的出口每条边有一个非负权值 代表策策经过这条边所要花的时间。
策策每天都会去逛公园他总是从 1 1 1 号点进去从 N N N 号点出来。
策策喜欢新鲜的事物它不希望有两天逛公园的路线完全一样同时策策还是一个 特别热爱学习的好孩子它不希望每天在逛公园这件事上花费太多的时间。如果 1 1 1 号点 到 N N N 号点的最短路长为 d d d那么策策只会喜欢长度不超过 d K d K dK 的路线。
策策同学想知道总共有多少条满足条件的路线你能帮帮它吗
为避免输出过大答案对 P P P 取模。如果有无穷多条合法的路线请输出 − 1 -1 −1。
输入格式
第一行包含一个整数 T T T, 代表数据组数。
接下来 T T T 组数据对于每组数据 第一行包含四个整数 N , M , K , P N,M,K,P N,M,K,P每两个整数之间用一个空格隔开。
接下来 M M M 行每行三个整数 a i , b i , c i a_i,b_i,c_i ai,bi,ci代表编号为 a i , b i a_i,b_i ai,bi 的点之间有一条权值为 c i c_i ci 的有向边每两个整数之间用一个空格隔开。
输出格式
输出文件包含 T T T 行每行一个整数代表答案。
【测试数据与约定】
对于不同的测试点我们约定各种参数的规模不会超过如下
测试点编号 T T T N N N M M M K K K是否有 0 0 0 边 1 1 1 5 5 5 5 5 5 10 10 10 0 0 0否 2 2 2 5 5 5 1 0 3 10^3 103 2 × 1 0 3 2\times 10^3 2×103 0 0 0否 3 3 3 5 5 5 1 0 3 10^3 103 2 × 1 0 3 2\times 10^3 2×103 50 50 50否 4 4 4 5 5 5 1 0 3 10^3 103 2 × 1 0 3 2\times 10^3 2×103 50 50 50否 5 5 5 5 5 5 1 0 3 10^3 103 2 × 1 0 3 2\times 10^3 2×103 50 50 50否 6 6 6 5 5 5 1 0 3 10^3 103 2 × 1 0 3 2\times 10^3 2×103 50 50 50是 7 7 7 5 5 5 1 0 5 10^5 105 2 × 1 0 5 2\times 10^5 2×105 0 0 0否 8 8 8 3 3 3 1 0 5 10^5 105 2 × 1 0 5 2\times 10^5 2×105 50 50 50否 9 9 9 3 3 3 1 0 5 10^5 105 2 × 1 0 5 2\times 10^5 2×105 50 50 50是 10 10 10 3 3 3 1 0 5 10^5 105 2 × 1 0 5 2\times 10^5 2×105 50 50 50是
对于 100 % 100\% 100% 的数据 1 ≤ P ≤ 1 0 9 1 \le P \le 10^9 1≤P≤109 1 ≤ a i , b i ≤ N 1 \le a_i,b_i \le N 1≤ai,bi≤N 0 ≤ c i ≤ 1000 0 \le c_i \le 1000 0≤ci≤1000。
数据保证至少存在一条合法的路线。 2019.8.30 增加了一组 hack 数据 by skicean2022.7.21 增加了一组 hack 数据 by djwj233
题目分析
关于方案数的统计我们考虑动态规划令 F [ y ] [ k ] F[y][k] F[y][k]表示从起点到 y y y比最短路多 k k k 的长度的路径方案数。状态转移 F [ y ] [ k ] ∑ d i s t [ x ] t w ( x , y ) d i s t [ y ] k F [ x ] [ t ] F[y][k] \sum_{dist[x]tw(x,y)dist[y]k} F[x][t] F[y][k]∑dist[x]tw(x,y)dist[y]kF[x][t]。对于这样的转移我们需要按照一定的顺序我们发现我们的阶段是 k k k, 即我们要先算 F [ 1... n ] [ 0 ] F[1...n][0] F[1...n][0]再算 F [ 1... n ] [ 1 ] F[1...n][1] F[1...n][1]以此类推。
我们不妨直接写成记忆化搜索这样我们就可以忽略顺序的问题了。记忆化搜索的入口是直接从第 n n n 个点开始往前回溯在返回时更新状态我们需要一张与原图完全相反的图。
关于无穷多合法路线的理解图中含有 0 0 0 环且和答案有关的路径有关系这个需要单独判断。如果有 0 0 0 环我们在记忆化搜索时会重复访问到 F [ y ] [ k ] F[y][k] F[y][k]我们在记忆化搜索中加一个访问标记即可。
启发
关于最短路有要求多少条边的(如牛站)有路径条数计数或方案计数的(如习题 R O A D ROAD ROAD)或是要将 d i s t dist dist限制在某一区间里的(如上一道例题 P e r m u t a t i o n Permutation Permutation P u z z l e Puzzle Puzzle)一般都用到了动态规划递推求解区别在于阶段和状态的表示与转移不同。可见对于类似的这类问题我们一般会通过分解为子问题的方式通过动规来求解在比赛中遇到此类问题需要有一定的灵敏性。
欧拉回路
差分约束系统
差分约束系统是一中特殊的 N N N元一次不等式组。它包含 N N N 个变量 X 1 X_1 X1~ X N X_N XN 以及 M M M 个约束条件每个约束条件都形如 X i − X j ≤ c k X_i-X_j\le c_k Xi−Xj≤ck 其中 c k c_k ck 是常数。我们的问题就是求一组解 X 1 , X 2 , . . . , X N X_1,X_2,...,X_N X1,X2,...,XN 是所有的约束条件满足或确定其无解。 e g 1 : eg1: eg1: P3275 SCOI2011 糖果 - 洛谷差分约束
题目大意
幼儿园里有 N N N 个小朋友 lxhgww \text{lxhgww} lxhgww 老师现在想要给这些小朋友们分配糖果要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心总是会提出一些要求比如小明不希望小红分到的糖果比他的多于是在分配糖果的时候 lxhgww \text{lxhgww} lxhgww 需要满足小朋友们的 K K K 个要求。幼儿园的糖果总是有限的 lxhgww \text{lxhgww} lxhgww 想知道他至少需要准备多少个糖果才能使得每个小朋友都能够分到糖果并且满足小朋友们所有的要求。
输入格式
输入的第一行是两个整数 N N N K K K。接下来 K K K 行表示这些点需要满足的关系每行 3 3 3 个数字 X X X A A A B B B。
如果 X 1 X1 X1 表示第 A A A 个小朋友分到的糖果必须和第 B B B 个小朋友分到的糖果一样多如果 X 2 X2 X2 表示第 A A A 个小朋友分到的糖果必须少于第 B B B 个小朋友分到的糖果如果 X 3 X3 X3 表示第 A A A 个小朋友分到的糖果必须不少于第 B B B 个小朋友分到的糖果如果 X 4 X4 X4 表示第 A A A 个小朋友分到的糖果必须多于第 B B B 个小朋友分到的糖果如果 X 5 X5 X5 表示第 A A A 个小朋友分到的糖果必须不多于第 B B B 个小朋友分到的糖果
输出格式
输出一行表示 lxhgww \text{lxhgww} lxhgww 老师至少需要准备的糖果数如果不能满足小朋友们的所有要求就输出 − 1 -1 −1。
对于 30 % 30\% 30% 的数据保证 N ≤ 100 N\leq100 N≤100
对于 100 % 100\% 100% 的数据保证 N ≤ 100000 N\leq100000 N≤100000
对于所有的数据保证 K ≤ 100000 , 1 ≤ X ≤ 5 , 1 ≤ A , B ≤ N K\leq100000, 1\leq X\leq5, 1\leq A, B\leq N K≤100000,1≤X≤5,1≤A,B≤N 洛谷 upd 2022.7.6 \text{upd 2022.7.6} upd 2022.7.6新添加 21 21 21 组 Hack 数据。
ac 代码参考代码查看 (nowcoder.com) 0 / 1 0/1 0/1 分数规划
A-Sightseeing Cows(nowcoder.com)spfa判负环二分求解01分数规划问题
练习题
2023_ICPC_杭州站 - G - Codeforces(1/2个银牌题)
B-Intervals_0x65 图论-负环与差分约束差分约束
[ 1044 − H A O I 2012 1044-HAOI2012 1044−HAOI2012]ROAD (nowcoder.com)最短路加动态规划
D-Tokitsukaze and Slash Draw_2024牛客寒假集训营2 (% n n n下的最短路 or DP)
1020-胖胖的牛牛 (nowcoder.com) (拆点建图思想) 1941 G − C o d e f o r c e s 1941G - Codeforces 1941G−Codeforces ( r a t i n g 2000 rating\ 2000 rating 2000)
三、树论以及图的联通性
最小生成树 e g 1 : eg1: eg1: A-走廊泼水节(nowcoder.com)克鲁斯卡尔思想的灵活运用
题目大意
给定一棵N个节点的树要求增加若干条边把这棵树扩充为完全图并满足图的唯一最小生成树仍然是这棵树。 求增加的边的权值总和最小是多少。 e g 2 eg2 eg2B-Picnic Planning (nowcoder.com)码量较大
题目大意 生成树计数 L C A LCA LCA、树上差分及应用
知识点
树的直径 树形DP两次 B F S BFS BFS 注意运用条件 L C A LCA LCA 树上倍增法 T a r j a n Tarjan Tarjan 算法 (离线算法)
例题 e g 1 : eg1: eg1: 巡逻 树的直径
题目大意
待更新 e g 2 : eg2: eg2: 闇の連鎖_(树上差分)
题目大意 根据题意“主要边”构成一棵树“附加边”是非树边。把一条附加边 ( x , y ) (x,y) (x,y) 添加到树上会构成一个环如过一开始切断 x x x~ y y y 路径上的一条边那么第二条必须切断 ( x , y ) (x,y) (x,y) 才能将 D a r k Dark Dark 分为不连通的两部分。我们可以考虑 ( x , y ) (x,y) (x,y) 把 x x x~ y y y 路径上的树边覆盖了一次那么如果我们第一次切掉覆盖数为 0 0 0 的树边 那么之后切任意一条非树边即可如果我们切掉覆盖数为 1 1 1 的树边第二步的切分唯一其余情况无法将 D a r k Dark Dark 分为不连通的两部分。
由上述分析可知我们要解决问题的模型就是在给定的一张无向图和一课生成树求非树边将树边覆盖了多少次。解决这一问题的经典做法就是“树上差分”。给定每个结点的权值初值为 0 0 0对于每条非树边 ( x , y ) (x,y) (x,y) 我们让 v a l x 1 , v a l y 1 , v a l l c a ( x , y ) − 2 val_x1,\ val_y1,\ val_{lca(x,y)}-2 valx1, valy1, vallca(x,y)−2最后用树形DP做一次 “子树前缀和” 即可得到每条树边的覆盖次数然后统计即可得到答案。
关于时间复杂度考虑用树上倍增法求 L C A LCA LCA复杂度为 O ( n log n ) O(n\log n) O(nlogn)。对于覆盖次数的预处理和答案求解需要遍历整张图复杂度为 O ( n m ) O(nm) O(nm)。总的时间复杂度为 O ( n m n log n ) O(nmn\log n) O(nmnlogn)。
启发 如果我们需要对树上的一条路径的每条边加上一个 d d d我们可以转化为 v a l x d , v a l y d , v a l l c a ( x , y ) − 2 d val_xd,\ val_yd,\ val_{lca(x,y)}-2d valxd, valyd, vallca(x,y)−2d。 e g 3 : eg3: eg3: E-天天爱跑步 e g 4 : eg4: eg4: F-异象石_ e g 5 : eg5: eg5: G-次小生成树_ e g 6 : eg6: eg6: H-疫情控制_
基环树 e g 1 : eg1: eg1: 岛屿_
题目大意 e g 2 : eg2: eg2: B-创世纪_
题目大意 e g 3 : eg3: eg3:K-牛镇公务员考试基环树一般的处理方式
题目大意 e g 4 : S u g a r S w e e t I I eg4:Sugar\ Sweet II eg4:Sugar SweetII 2023_ICPC_杭州站 - H - Codeforces基环树 概率1/2个银牌题
题目大意
Sugar is sweet. There are n n n children asking for sugar. Prof. Chen gives out sugar to the children. The i i i-th child initially has a i a_{i} ai bags of sugar. There are n n n events happening in uniformly randomized order. The i i i-th event is:
If the i i i-th child has strictly less bags of sugar than the b i b_{i} bi-th child, then the i i i-th child will get extra w i w_{i} wi bags of sugar. Otherwise, nothing happens.
Now, since the events happen in random order, Randias, which is the assistant of Prof. Chen, wants to know the expected number of bags of sugar each child will have after all the events happen.
It can be shown that the answer can be expressed as an irreducible fraction x y \frac{x}{y} yx where x x x and y y y are integers and y ≢ 0 ( m o d 1 0 9 7 ) y \not \equiv 0 \pmod {10^9 7} y≡0(mod1097). Output the integer equal to x ⋅ y − 1 ( m o d 1 0 9 7 ) x \cdot y^{-1} \pmod {10^9 7} x⋅y−1(mod1097). In other words, output such an integer a a a that 0 ≤ a 1 0 9 7 0\leq a 10^9 7 0≤a1097 and a ⋅ y ≡ x ( m o d 1 0 9 7 ) a \cdot y \equiv x \pmod {10^9 7} a⋅y≡x(mod1097).
练习题
B-树网的核_0x63 图论-树的直径与最近公共祖先
C-最优比率生成树_0x62 图论-最小生成树 (0/1分数规划)
D-雨天的尾巴 (树上差分的综合运用)
四、二分图及图匹配
二分图常见模型
二分图判定 黑白染色不含奇圈点可以分成左右两部份每一部份内没有边 最大匹配 增广路算法匈牙利算法最小点覆盖最大独立集最小路径覆盖 带权匹配 KM算法 二分图与网络流的联系
二分图例题 e g 1 : eg1: eg1: [ Z J O I 2009 ZJOI2009 ZJOI2009]假期的宿舍(二分图最大匹配板题)
题目大意 e g 2 : eg2: eg2: C-Going Home二分图带权匹配KM算法
题目大意 e g 3 : eg3: eg3: 棋盘覆盖蓝书例题
题目大意
给定一个 N N N行 N N N列的棋盘已知某些格子禁止放置。求最多能往棋盘上放多少块的长度为 2 2 2、宽度为 1 1 1 的骨牌。骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。 N , M ≤ 100 N,M≤100 N,M≤100。 e g 4 : eg4: eg4: L-城市物流cf上也有对应原题rating 2600二分图匹配模型综合题
题目大意 一般图匹配
练习题
A-情侣和聚餐(cf上也有对应题目2600 二分图构造)
D-炸弹二分图最大匹配
[E-ZJOI2007]矩阵游戏二分图最大匹配
G-画圈游戏
H-占领城市(最小路径覆盖拆点跑最大匹配或最大流)
I-中心图思维暴力二分图匹配
J-插座思维暴力二分图匹配
五、网络流初步
网络流的核心在于建图。建图是精髓也是难点。网络流的建图方法一定程度上刻画了贪心问题的内在性质从而简便地支持了反悔不需要我们为每道贪心问题都寻找反悔策略。
最大流Maximum flow简称 M F MF MF e g 1 : eg1: eg1: P 2764 P2764 P2764 最小路径覆盖问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目大意
(启发对于限制了点的出入度都为1的时候我们可以将一个点拆成一个入点和一个出点)
最小费用最大流Minimum cost maximum flow简称 M C M F MCMF MCMF
常见的建模思路
六、综合模型及应用(以题目总结为主)
分层图思想 e g 1 : 通信线路 eg1:通信线路 eg1:通信线路A-Telephone Lines(蓝书例题)
题目大意 解法一动态规划
仿照动态规划的思想用 d i s t [ x , i ] dist[x,i] dist[x,i] 表示从 1 1 1 到达 x x x途中已经指定了 i i i 条电缆免费时经过路径上最贵的边的花费的最小值。若有一条边 w ( x , y ) w(x,y) w(x,y) 则 d i s t [ y , i ] max ( d i s t [ x , i ] , w ) dist[y,i] \max(dist[x,i],w) dist[y,i]max(dist[x,i],w) d i s t [ y , i 1 ] d i s t [ x , i ] dist[y,i1] dist[x,i] dist[y,i1]dist[x,i]。两个式子分别表示不用免费的升级服务用一次免费的升级服务。可以看到我们的状态转移明显是有后效性的一种解决方案是利用迭代的思想借助 S P F A SPFA SPFA算法就行动规直至所有状态收敛。对于特殊构造的数据 S P F A SPFA SPFA 的时间复杂度可能退化为 O ( N M ) O(NM) O(NM)谨慎使用。
解法二分层图最短路
从最短路问题的角度去理解图中的结点可以扩展到二维元组 ( x , i ) (x,i) (x,i) 表示一个结点。对于边 w ( x , y ) w(x,y) w(x,y)我们可以在分层图中 ( x , i ) (x,i) (x,i) 到 ( y , i 1 ) (y,i1) (y,i1) 连一条边权为 0 0 0 的有向边那么我们就构造出了一个 N × K N\times K N×K 个点 ( N P ) × K (NP)\times K (NP)×K 条边的分层图。其中不同层之间的有向边帮助我们确保了答案的计算只能从低层向高层转移解决了后效性问题。这类广义的最短路问题被称为分层图最短路问题我们可以直接在分层图上跑 D i j k s t r a Dijkstra Dijkstra 即可得到答案。 时间复杂度为 O ( ( N P ) K log ( N K ) ) O((NP)K\log(NK)) O((NP)Klog(NK))。
解法三二分答案 01 B F S 01BFS 01BFS
我们进一步思考本题答案的性质当支付的钱更多时合法的升级方案一定包含了花费更少的升级方案也就是说当 K K K 确定时我们花费的钱更多合法的方案也就更多方案数有单调性我们考虑二分答案那么问题就转化为是否存在合法的方案使得花费不超过 m i d mid mid。
对于 c h e a k cheak cheak 函数我们只需要将花费小于等于 m i d mid mid 的边权设为 0 0 0其余设为 1 1 1我们可以用双端队列 B F S BFS BFS 求出边权只包含 0 / 1 0/1 0/1 的单源最短路问题。判断是否 d i s t [ n ] ≤ K dist[n]\le K dist[n]≤K 即可。时间复杂度为 O ( ( N P ) log max L ) O((NP)\log \max_L) O((NP)logmaxL)
ac代码参考分层图最短路 、二分答案 01 B F S 01BFS 01BFS e g 2 : 小雨坐地铁 eg2:小雨坐地铁 eg2:小雨坐地铁 1012-小雨坐地铁(nowcoder.com)
题目大意 e g 3 : G . B i c y c l e s eg3: G. Bicycles eg3:G.Bicycles Problem - 1915G - Codeforces(注意带点贪心剪枝)
题目大意
All of Slavic’s friends are planning to travel from the place where they live to a party using their bikes. And they all have a bike except Slavic. There are n n n cities through which they can travel. They all live in the city 1 1 1 and want to go to the party located in the city n n n. The map of cities can be seen as an undirected graph with n n n nodes and m m m edges. Edge i i i connects cities u i u_i ui and v i v_i vi and has a length of w i w_i wi.
Slavic doesn’t have a bike, but what he has is money. Every city has exactly one bike for sale. The bike in the i i i-th city has a slowness factor of s i s_{i} si. Once Slavic buys a bike, he can use it whenever to travel from the city he is currently in to any neighboring city, by taking w i ⋅ s j w_i \cdot s_j wi⋅sj time, considering he is traversing edge i i i using a bike j j j he owns.
Slavic can buy as many bikes as he wants as money isn’t a problem for him. Since Slavic hates traveling by bike, he wants to get from his place to the party in the shortest amount of time possible. And, since his informatics skills are quite rusty, he asks you for help.
What’s the shortest amount of time required for Slavic to travel from city 1 1 1 to city n n n? Slavic can’t travel without a bike. It is guaranteed that it is possible for Slavic to travel from city 1 1 1 to any other city. e g 4 : R i n n e L o v e s G r a p h eg4: Rinne\ Loves\ Graph eg4:Rinne Loves Graph NC22594, 1031-Rinne Loves Graph(nowcoder.com)
题目大意 rating 2400
平面图思想
最短路图
其他
拆点建图
搭平台建图 e g 1 : eg1: eg1:Meeting (nowcoder.com)(UVALive7250 / hduoj 552115年沈阳站银牌题)
题目大意 输入描述注意数据范围
The first line contains an integer T ( 1 ≤ T ≤ 6 ) T (1≤T≤6) T(1≤T≤6), the number of test cases. Then T T T test cases follow.
The first line of input contains n n n and m m m. 2 ≤ n ≤ 1 0 5 2≤n≤10^5 2≤n≤105. The following m lines describe the sets E i ( 1 ≤ i ≤ m ) E_i (1≤i≤m) Ei(1≤i≤m). Each line will contain two integers t i ( 1 ≤ t i ≤ 1 0 9 ) t_i(1≤t_i≤10^9) ti(1≤ti≤109) and S i ( S i 0 ) S_i (S_i0) Si(Si0) firstly. Then S i S_i Si integer follows which are the labels of blocks in E i E_i Ei. It is guaranteed that ∑ S i ≤ 1 0 6 ∑S_i≤10^6 ∑Si≤106. e g 2 : eg2: eg2: Problem - 1941G - Codeforces(搭平台跑最短路相当于把图集合化cf rating 2000)
题目大意
Building bridges did not help Bernard, and he continued to be late everywhere. Then Rudolf decided to teach him how to use the subway.
Rudolf depicted the subway map as an undirected connected graph, without self-loops, where the vertices represent stations. There is at most one edge between any pair of vertices.
Two vertices are connected by an edge if it is possible to travel directly between the corresponding stations, bypassing other stations. The subway in the city where Rudolf and Bernard live has a color notation. This means that any edge between stations has a specific color. Edges of a specific color together form a subway line. A subway line cannot contain unconnected edges and forms a connected subgraph of the given subway graph.
An example of the subway map is shown in the figure. Rudolf claims that the route will be optimal if it passes through the minimum number of subway lines. Help Bernard determine this minimum number for the given departure and destination stations.
最小树形图 e g 1 : eg1: eg1: [1036-[ S C O I 2012 SCOI2012 SCOI2012] 滑雪与时间胶囊](https://ac.nowcoder.com/acm/contest/26077/1036)
题目大意 模型综合运用练习题
Problem - J - Codeforces( 2022 C C P C 2022CCPC 2022CCPC桂林金牌题拓扑排序DP贪心)
Problem - G - Codeforces( 2021 C C P C 2021CCPC 2021CCPC哈尔滨银牌题最短路状压期望DP)
Problem - J - Codeforces 2023 I C P C 2023ICPC 2023ICPC山东省赛金牌题图论背景位运算类似于数位DP的思想
参考资料
1、OI Wiki
2、李煜东 《算法竞赛进阶指南》
3、邓丝雨 牛客图论专题班教案
最小树形图 e g 1 : eg1: eg1: [1036-[ S C O I 2012 SCOI2012 SCOI2012] 滑雪与时间胶囊](https://ac.nowcoder.com/acm/contest/26077/1036)
题目大意
[外链图片转存中…(img-2AC2GtNF-1713345898274)]
模型综合运用练习题
Problem - J - Codeforces( 2022 C C P C 2022CCPC 2022CCPC桂林金牌题拓扑排序DP贪心)
Problem - G - Codeforces( 2021 C C P C 2021CCPC 2021CCPC哈尔滨银牌题最短路状压期望DP)
Problem - J - Codeforces 2023 I C P C 2023ICPC 2023ICPC山东省赛金牌题图论背景位运算类似于数位DP的思想
参考资料
1、OI Wiki
2、李煜东 《算法竞赛进阶指南》
3、邓丝雨 牛客图论专题班教案
4、 【 a l e x − w e i 】 【alex-wei】 【alex−wei】网络流二分图与图的匹配
