前言六、综合模型及应用(以题目总结为主)分层图思想(包括拆点建图)

Lines](https://ac.nowcoder.com/acm/contest/1055/A)(蓝书例题)

小雨坐地铁

[1012-小雨坐地铁(nowcoder.com)](https://ac.nowcoder.com/acm/contest/26077/1012)

eg3:

Codeforces](https://codeforces.com/problemset/problem/1915/G)(注意带点贪心剪枝)

eg4:

Graph(nowcoder.com)](https://ac.nowcoder.com/acm/contest/26077/1031)

平面图思想最短路图其他一些综合题

Tree](https://ac.nowcoder.com/acm/contest/80999/C)2020牛客多校第十场

2024牛客五一集训派对Day

2021牛客暑期多校2](https://ac.nowcoder.com/acm/contest/81001/K)

eg4:Permutation\

](https://codeforces.com/gym/104008/problem/J)(金牌题拓扑排序DP贪心)

搭平台建图

(nowcoder.com)](https://ac.nowcoder.com/acm/contest/26077/1022)(UVALive7250

hduoj

Codeforces](https://codeforces.com/problemset/problem/1941/G)(搭平台跑最短路相当于把图集合化cf

rating

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

模型综合运用练习题

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

XCPC)

dist[y,i1]dist[x,i]。

两个式子分别表示不用免费的升级服务用一次免费的升级服务。

可以看到我们的状态转移明显是有后效性的一种解决方案是利用迭代的思想借助

SPFA

条边的分层图。

其中不同层之间的有向边帮助我们确保了答案的计算只能从低层向高层转移解决了后效性问题。

这类广义的最短路问题被称为分层图最短路问题我们可以直接在分层图上跑

Dijkstra

我们进一步思考本题答案的性质当支付的钱更多时合法的升级方案一定包含了花费更少的升级方案也就是说当

确定时我们花费的钱更多合法的方案也就更多方案数有单调性我们考虑二分答案那么问题就转化为是否存在合法的方案使得花费不超过

mid

题目大意是给你一棵树要支持边权修改每次操作选一条路径把路径上的边权全部减少

0​​

的最小次数。

读完题我们发现其实我们要将这棵树拆分成诺干条简单路径。

这样我们就转化成每个点需要占用多少次路径使其减为一我们可以考虑点的连边情况我们可以贪心的想对于一个点的出和入能多匹配就多匹配。

怎么使其能覆盖就覆盖呢

max

看到在带边权的树上操作我们一个惯用的套路就是边权转点权。

这样我们只需要把这些加起来除个2就好了。

边权修改的话

ac代码参考代码查看

拓扑排序DP求最短路的构造题想到图论不难难点是想到用图论算法这么做。

根据所给限制建图将

个互不相同的数我们需要给每个数匹配一个包含它的区间此外每个区间匹配的数还要满足一些拓扑关系(形如

P_uP_v

Pu​Pv​的约束)。

如果暂时不考虑拓扑关系的话是一个经典问题存在一个简单的贪心做法从小到大枚举所有数当枚举到

时从所有左端点

Pu​Pv​。

所以直接贪心求出来的就是原问题的合法解如果贪心无解则原问题一定无解。

总时间复杂度

拓扑排序DP将答案优化到一个区间内此时可能会将问题转化为另一个较简单直白的问题如本题转化为了一个简单的贪心问题。

当然对于一些构造题可能对于一些限制条件使得答案符合一种拓扑关系即可考虑使用拓扑排序限制合法答案或直接进行构造。

ac代码参考[Submission

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

题目大意

2023ICPC山东省赛金牌题图论背景位运算类似于数位DP的思想