网站用nodejs做后台,建中英文网站,拉新项目官方一手平台,永康信誉好关键词优化文章目录 前言六、综合模型及应用(以题目总结为主)分层图思想(包括拆点建图) e g 1 : 通信线路 eg1:通信线路 eg1:通信线路[A-Telephone Lines](https://ac.nowcoder.com/acm/contest/1055/A)(蓝书例题) e g 2 : 小雨坐地铁 eg2:小雨坐地铁 eg2:小雨坐地铁 [1012-小雨坐… 文章目录 前言六、综合模型及应用(以题目总结为主)分层图思想(包括拆点建图) 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: [C-Decrement on the Tree](https://ac.nowcoder.com/acm/contest/80999/C)2020牛客多校第十场 / 2024牛客五一集训派对Day 3 e g 3 : eg3: eg3: [K-Stack_2024牛客五一集训day5 / 2021牛客暑期多校2](https://ac.nowcoder.com/acm/contest/81001/K) e g 4 eg 4 eg4:Permutation\ Puzzle $ [ 2022 C C P C G u i l i n − J 2022\ CCPC\ Guilin - J 2022 CCPC Guilin−J ](https://codeforces.com/gym/104008/problem/J)(金牌题拓扑排序DP贪心) 搭平台建图 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) 模型综合运用练习题 前言
由于图论学习总结内容过多全放在一篇博客过于冗长现进行拆分本文是综合模型及应用部分其他部分地址见图论学习总结(For XCPC)
六、综合模型及应用(以题目总结为主)
分层图思想(包括拆点建图) 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: C-Decrement on the Tree2020牛客多校第十场 / 2024牛客五一集训派对Day 3
题面 题目分析
题目大意是给你一棵树要支持边权修改每次操作选一条路径把路径上的边权全部减少 1 1 1。问减到 0 0 0 的最小次数。读完题我们发现其实我们要将这棵树拆分成诺干条简单路径。这样我们就转化成每个点需要占用多少次路径使其减为一我们可以考虑点的连边情况我们可以贪心的想对于一个点的出和入能多匹配就多匹配。怎么使其能覆盖就覆盖呢 如果 m a x ≤ s u m / 2 max \le sum/2 max≤sum/2则会多出 s u m % 2 sum\%2 sum%2 的数量如果 m a x s u m / 2 maxsum/2 maxsum/2则会多出 2 × m a x − s u m 2\times max-sum 2×max−sum 的数量 看到在带边权的树上操作我们一个惯用的套路就是边权转点权。这样我们只需要把这些加起来除个2就好了。边权修改的话
ac代码参考代码查看 (nowcoder.com) e g 3 : eg3: eg3: K-Stack_2024牛客五一集训day5 / 2021牛客暑期多校2
题目大意 题目分析 e g 4 eg 4 eg4:Permutation\ Puzzle $ 2022 C C P C G u i l i n − J 2022\ CCPC\ Guilin - J 2022 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 上存在一条从 到 的边数为 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对于边 (, )做转移 L v max ( L v , L u 1 ) L_v \max(L_v, L_u 1) Lvmax(Lv,Lu1)然后反向拓扑排序求出 R R R对于边 (, )做转移 R u min ( R u , R v − 1 ) R_u \min(R_u, R_v − 1) Rumin(Ru,Rv−1)。
于是转化为如下问题给定 个区间和 个互不相同的数我们需要给每个数匹配一个包含它的区间此外每个区间匹配的数还要满足一些拓扑关系(形如 P u P v P_uP_v PuPv的约束)。如果暂时不考虑拓扑关系的话是一个经典问题存在一个简单的贪心做法从小到大枚举所有数当枚举到 时从所有左端点 ≤ x ≤ x ≤x 且还没被匹配的区间中选择右端点最小的那个匹配给 这个过程用优先队列优化。
然后分析一下区间的性质如果存在边 (, )根据转移方程可得 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 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)
题目大意 模型综合运用练习题
回家的路 洛谷 P 3831 P3831 P3831 [ S H O I 2012 ] [SHOI2012] [SHOI2012]
Problem - G - Codeforces( 2021 C C P C 2021CCPC 2021CCPC哈尔滨银牌题最短路状压期望DP)
Problem - B - Codeforces( 2023 I C P C 2023ICPC 2023ICPC山东省赛金牌题拓扑排序优先队列优化
Problem - J - Codeforces 2023 I C P C 2023ICPC 2023ICPC山东省赛金牌题图论背景位运算类似于数位DP的思想
