wxwoo's blog

原题目链接

首先树剖边权转点权，把每一条边的权值下放到子节点上

在修改的时候注意最后要避开两个点的LCA，因为LCA的点权所代表的边权不在两个点的路径上

然后看见区间推平就想到了ODT

原题目链接

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

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

此题关键点：

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

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

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

……吗？

原题目链接

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

最大权闭合子图：

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

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

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

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

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

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

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

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

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

原题目链接

选人有利润，选了要付出代价：明显的最小割模型

我们将每个人看成一个点，然后如下建边：

1. 源点向每个人连流量为其总收益的边（即$\sum\limits_{j=1}^n E_{i,j}$）

2. 每个人向汇点连流量为其花费的边

3. $i$向$j$连流量为$E_{i,j} \times 2$的边

原题目链接

每张合影可选可不选，选了必须带一些特定人：明显的最大权闭合子图

最大权闭合子图：

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

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

原题目链接

蒟蒻提供一个思路：

理论上，我们可以将

1
2
3
4
5

    ________
   |   __   |
   |  |  |  |
---------------->
   2  5  9  11

的重叠覆盖情况看成

1
2
3
4
5

    _____
   |   __|__
   |  |  |  |
---------------->
   2  5  9  11

所以，若我们将起点和终点按照从小到大的顺序排序，对答案不会产生影响

原题目链接

将狼和羊分成两个部分：明显的最小割

根据最大流最小割定理，最大流=最小割，所以这题可以使用最大流算法求解

我们将每个格子看成一个点，然后如下建边：

1. 源点向狼的领地连流量为$inf$的边

2. 羊的领地向汇点连流量为$inf$的边

3. 每个格子向上下左右四个格子连流量为$1$的边

原题目链接

洛谷随机跳题跳到的

有指向，有修改，求最小：明显的最小费用最大流

我们将每个格子看成一个点，然后拆点，如下建边：

1. 源点向每个点连边，流量为1，费用为0

2. 每个点的拆点向汇点连边，流量为1，费用为0

3. 每个点向四周的点连边，流量为1，默认指向费用为0，其他为1