原题目链接

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

最大权闭合子图：

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

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

原题目链接

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

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

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

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

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

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

原题目链接

看到题目就想到了dfs+剪枝

然后就想到了dfs有问题

例如这组数据

1
2
3

4-9-12
| | |
2-4-10

从4开始，到10结束

dfs会走$4 \to 2 \to 4 \to 10$，答案为8

然而很明显走$4 \to 9 \to 4 \to 10$更优，答案为6

当然你加一大堆玄学优化也是可以搜出正确答案的

这里不再多讲，而是提供另一种思路：

二分

原题目链接

写这题翻译的时候，突然就有了思路

实际上这题重在思考

若a机场和b机场是同一家公司，输出0，这个很容易想到

若a机场和b机场不是同一家公司，输出1，这是为什么呢？

原题目链接

蒟蒻提供一个思路：

理论上，我们可以将

1
2
3
4
5

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

的重叠覆盖情况看成

1
2
3
4
5

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

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

原题目链接

洛谷随机跳题跳到的

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

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

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

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

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

原题目链接

我们可以取两条线段的中点，若重合就让第二条线段的中点+1

$Q:$中点+1后不在线段上怎么办？

$A:$由于C++整数除法自动省略小数，也就是向下取整，若线段长度大于1，那么中点+1后一定不会超出线段，若线段长度为1，即$l+1=r$，那么$\left\lfloor\dfrac{l+r}{2}\right\rfloor=l$，所以中点$+1=r$，也不会超出线段，所以中点+1后无论如何都在线段上，符合题意

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.