wxwoo's blog

评论系统

链接请填写OJ账户(luogu优先),选填
邮箱用于验证和回复通知,必须填写
无法匿名评论
头像请用你的邮箱,到Gravatar设置
由于评论管理系统尚未部署完成(其实就是咕咕咕了),不一定会发送邮件

原题目链接

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

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

此题关键点:

小明和小红的生活中,有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

在使用hexo博客和material-x等博客主题时,难免会遇到mathjax数学公式渲染失败或者与markdown渲染冲突的问题。

xaoxuu给出了解决方案,只需在_config.yml里加入mathjax: true即可解决,可以解决大量的mathjax公式渲染,但仍有部分复杂的公式渲染出现问题。

我在这里给出一种解决方案。

注:部分资料来自互联网


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


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

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