综合模型及应用(图论学习总结部分内容)

前言

由于图论学习总结内容过多，全放在一篇博客过于冗长现进行拆分，本文是综合模型及应用部分，其他部分地址见：图论学习总结(For XCPC)

六、综合模型及应用(以题目总结为主)

分层图思想(包括拆点建图)

$eg1:通信线路$​​​A-Telephone Lines(蓝书例题)

题目大意

解法一：动态规划

​ 仿照动态规划的思想，用$dist[x,i]$ 表示从 $1$ 到达 $x$，途中已经指定了 $i$ 条电缆免费时，经过路径上最贵的边的花费的最小值。若有一条边 $w(x,y)$ 则 $dist[y,i]=\max (dist[x,i],w)$，$dist[y,i+1]=dist[x,i]$。两个式子分别表示不用免费的升级服务，用一次免费的升级服务。可以看到我们的状态转移明显是有后效性的，一种解决方案是利用迭代的思想，借助$SPFA$算法就行动规，直至所有状态收敛。对于特殊构造的数据 $SPFA$ 的时间复杂度可能退化为 $O(NM)$，谨慎使用。

解法二：分层图最短路

​ 从最短路问题的角度去理解，图中的结点可以扩展到二维元组 $(x,i)$ 表示一个结点。对于边 $w(x,y)$，我们可以在分层图中 $(x,i)$ 到 $(y,i+1)$ 连一条边权为 $0$ 的有向边，那么我们就构造出了一个 $N\times K$ 个点 $(N+P)\times K$ 条边的分层图。其中不同层之间的有向边帮助我们确保了答案的计算只能从低层向高层转移，解决了后效性问题。这类广义的最短路问题被称为分层图最短路问题，我们可以直接在分层图上跑 $Dijkstra$ 即可得到答案。 时间复杂度为 $O((N+P)K\log (NK))$。

解法三：二分答案+$01BFS$

我们进一步思考本题答案的性质，当支付的钱更多时，合法的升级方案一定包含了花费更少的升级方案，也就是说当 $K$ 确定时，我们花费的钱更多，合法的方案也就更多，方案数有单调性，我们考虑二分答案，那么问题就转化为：是否存在合法的方案使得花费不超过$mid$。

​ 对于 $cheak$ 函数，我们只需要将花费小于等于 $mid$ 的边权设为 $0$，其余设为 $1$，我们可以用双端队列$BFS$ 求出边权只包含 $0/1$ 的单源最短路问题。判断是否 $dist[n]\le K$ 即可。时间复杂度为 $O((N+P)\log {\max }_L)$

ac代码参考：分层图最短路 、二分答案+$01BFS$

$eg2:小雨坐地铁$​ 1012-小雨坐地铁(nowcoder.com)

题目大意

$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$ cities through which they can travel. They all live in the city $1$ and want to go to the party located in the city $n$. The map of cities can be seen as an undirected graph with $n$ nodes and $m$ edges. Edge $i$ connects cities $u_i$ and $v_i$ and has a length of $w_i$.

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$-th city has a slowness factor of $s_i$. 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\cdot s_j$ time, considering he is traversing edge $i$ using a bike $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$ to city $n$? Slavic can’t travel without a bike. It is guaranteed that it is possible for Slavic to travel from city $1$​ to any other city.

$eg4:RinneLovesGraph$​ NC22594, 1031-Rinne Loves Graph(nowcoder.com)

题目大意

rating 2400

平面图思想

最短路图

其他

一些综合题

$eg1:$ C-Decrement on the Tree（2020牛客多校第十场 / 2024牛客五一集训派对Day 3）

题面

题目分析

• 题目大意是给你一棵树要支持边权修改，每次操作选一条路径，把路径上的边权全部减少 $1$。问减到 $0$​​ 的最小次数。
• 读完题我们发现，其实我们要将这棵树拆分成诺干条简单路径。
• 这样我们就转化成每个点需要占用多少次路径使其减为一，我们可以考虑点的连边情况，我们可以贪心的想，对于一个点的出和入能多匹配就多匹配。
• 怎么使其能覆盖就覆盖呢？
  • 如果 $max\le sum/2$，则会多出 $sum\%2$ 的数量
  • 如果 $max>sum/2$，则会多出 $2\times max-sum$​ 的数量
• 看到在带边权的树上操作，我们一个惯用的套路就是：边权转点权。
• 这样我们只需要把这些加起来除个2就好了。
• 边权修改的话

ac代码参考：代码查看 (nowcoder.com)

$eg3:$​ K-Stack_2024牛客五一集训day5 / 2021牛客暑期多校2

题目大意

题目分析

$eg4$:Permutation\ Puzzle $ $2022CCPCGuilin-J$ (金牌题，拓扑排序+DP+贪心)

题目大意

Little $relyt871$ is solving a puzzle. The key to the puzzle is a permutation containing numbers $1\dots n$. The values at some positions of the permutation are already fixed, and $relyt871$ needs to fill numbers into the remaining positions.

Besides, little $relyt871$ has gathered $m$ extra requirements about the permutation. Let the solution be represented as $p_1,p_2,...,p_n$, each clue is a pair of indices $(u_i,v_i)$, which means that $p_{u_i}<p_{v_i}$​ should be satisfied in the solution.

Little $relyt871$​ wonders if all requirements may be satisfied at the same time. Write a program to find a valid solution when there is one.

题目分析

​ 这是一道灵活运用$拓扑排序+DP$求最短路的构造题，想到图论不难，难点是想到用图论算法这么做。

​ 根据所给限制建图，将 $p_u<p_v$ 的限制视为一条 $u\to v$ 的单向边，题目保证会得到一个 $DAG$。 设在 $DAG$ 上存在一条从 𝑢 到 𝑣 的边数为 $k$ 的路径，若 $p_u$ 已知而 $p_v$ 未知，则可以推出 $p_v\ge p_u+k$； 若 $p_u$ 未知而 $p_v$ 已知，则可以推出 $p_u\le p_v-k$。 首先我们通过上述规则推导出所有位置的取值范围 $[L_i,R_i]$。对于已知位置，显然 $L_i=R_i=P_i$，对于未知位置，可以用$拓扑排序+dp$ 来求解。先正向拓扑排序求出 $L$：对于边 (𝑢, 𝑣)，做转移 $L_v=\max (L_v,L_u+1)$，然后反向拓扑排序求出 $R$：对于边 (𝑢, 𝑣)，做转移 $R_u=\min (R_u,R_v-1)$。

​ 于是转化为如下问题：给定 𝑘 个区间和 𝑘 个互不相同的数，我们需要给每个数匹配一个包含它的区间，此外每个区间匹配的数还要满足一些拓扑关系(形如$P_u<P_v$的约束)。如果暂时不考虑拓扑关系的话是一个经典问题，存在一个简单的贪心做法：从小到大枚举所有数，当枚举到 𝑥 时，从所有左端点 $\le x$ 且还没被匹配的区间中，选择右端点最小的那个匹配给 𝑥，这个过程用优先队列优化。

​ 然后分析一下区间的性质：如果存在边 (𝑢, 𝑣)，根据转移方程可得 $L_u+1\le L_v，R_u+1\le R_v$，按照上述贪心做法，$[L_u,R_u]$ 一定比 $[L_v,R_v]$ 更早被匹配到，即一定满足 $P_u<P_v$。所以直接贪心求出来的就是原问题的合法解，如果贪心无解则原问题一定无解。 总时间复杂度 $O(m+n\log n)$。

​ 启发：对于$拓扑排序+DP$不仅可以用来就$DAG$的最短路，对于这种可行解的构造问题，我们可以用$拓扑排序+DP$将答案优化到一个区间内，此时可能会将问题转化为另一个较简单直白的问题，如本题转化为了一个简单的贪心问题。当然，对于一些构造题，可能对于一些限制条件，使得答案符合一种拓扑关系，即可考虑使用拓扑排序限制合法答案，或直接进行构造。

ac代码参考：[Submission #256911647 - Codeforces

搭平台建图

$eg1:$Meeting (nowcoder.com)(UVALive7250 / hduoj 5521，15年沈阳站银牌题)

题目大意

输入描述，注意数据范围

The first line contains an integer $T(1\le T\le 6)$, the number of test cases. Then $T$ test cases
follow.

The first line of input contains $n$ and $m$. $2\le n\le 10^5$. The following m lines describe the sets $E_i(1\le i\le m)$. Each line will contain two integers $t_i(1\le t_i\le 10^9)$ and $S_i(S_i>0)$ firstly. Then $S_i$ integer follows which are the labels of blocks in $E_i$. It is guaranteed that $\sum S_i\le 10^6$​.

$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.

最小树形图

$eg1:$ [1036-[$SCOI2012$] 滑雪与时间胶囊](https://ac.nowcoder.com/acm/contest/26077/1036)

题目大意

模型综合运用练习题

回家的路 （洛谷 $P3831$ $[SHOI2012]$）

Problem - G - Codeforces($2021CCPC$哈尔滨，银牌题，最短路+状压期望DP)

Problem - B - Codeforces($2023ICPC$山东省赛，金牌题，拓扑排序，优先队列优化）

Problem - J - Codeforces（$2023ICPC$山东省赛，金牌题，图论背景+位运算，类似于数位DP的思想）