wxwoo's blog

原题目链接

此题显然为有向图判负权环板子题

没做过请先右转模板【负环】

此题关键点:

小明和小红的生活中,有N个关键的节点。有M个事件,记为一个三元组(Si,Ti,Wi),表示从节点Si有一个事件可以转移到Ti,事件的效果就是使他们之间的距离减少Wi。

所以建边时,要把权值变为相反数

然后以1为源点进行SPFA求负环,就AC了

……吗?

原题目链接

先无视租机器,明显的最大权闭合子图

最大权闭合子图:

给定一个有向图,点有点权,选择一个子图,满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。

我们将机器和任务都看成一个点

如果这题没有租机器,这题的建边方式就应该是这样:

  1. 源点向订单连流量为利润的边

  2. 机器向汇点连流量为购买价格的边

  3. 每个订单向需要的机器连流量为inf的边

可以发现,源点连的边都是订单的利润,汇点连的边都是机器的成本,只有机器和订单之间的边是$inf$

对于每个订单需要的相同机器,租用的价格也不一样

所以我们考虑把$inf$换成租机器的费用

原题目链接

明显的最大权闭合子图

最大权闭合子图:

给定一个有向图,点有点权,选择一个子图,满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。

经典的网络流问题,具体使用最小割求解

我们将顾客和通讯站都看成一个点,然后如下建边:

  1. 源点向顾客连流量为利润的边

  2. 通讯站向汇点连流量为成本的边

  3. 每个顾客向需要的通讯站连流量为inf的边

原题目链接

树上链最值查询

做法很多,LCT,树上倍增,树剖都可以

但由于LCT常数过大,树上倍增比树剖常数大,这里使用树链剖分

边权转点权是树剖常用套路,将边权转成深度较大的点的点权,查询时注意避开两点的LCA的权值

由于不带修改,树剖后用ST表维护,时间复杂度$\mathcal{O}(n\log n)$,比用线段树维护$\mathcal{O}(n\log ^2n)$还少一个log


载入天数...载入时分秒...


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 , 总访问量为 次 。