wxwoo's blog

原题目链接

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

最大权闭合子图：

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

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

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

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

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

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

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

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

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

原题目链接

明显的最大权闭合子图

最大权闭合子图：

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

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

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

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

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

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

原题目链接

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

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

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

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

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

原题目链接

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

最大权闭合子图：

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

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

原题目链接

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

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

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

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

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

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

原题目链接

洛谷随机跳题跳到的

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

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

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

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

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